打破一個字符串分割成詞序列

Question

我最近遇到下面的面試問題就來了：

給定的輸入字符串和單詞的字典，實施，打破了輸入字符串轉換爲節省空間的方法搜索引擎可能使用的單詞串詞典「你的意思是？」例如，「applepie」的輸入應該產生「蘋果派」的輸出。

就複雜性而言，我似乎無法獲得最佳解決方案。有沒有人有任何建議如何有效地做到這一點？

Answer 1

看起來這個問題恰恰是我的面試問題，直到我在嘈雜頻道的post中使用的例子。很高興你喜歡這個解決方案。我相當肯定你不能擊敗O（n^2）動態編程/記憶解決方案，我描述的最壞情況的性能。

如果你的字典和輸入不是病態的，你可以在實踐中做得更好。例如，如果您可以在線性時間內識別輸入字符串的子字符串在字典中（例如，，具有一個trie），如果這些子串的數目是恆定的，那麼總體時間將是線性的。當然，這是很多假設，但真實數據通常比病態最壞情況好得多。

也有一些有趣的變化使問題變得更加困難，例如枚舉所有有效的分割，根據某些最佳分割輸出最佳分割，處理一個太大而不適合內存的字典，以及處理不精確的分割（例如糾正拼寫錯誤）。隨時在我的博客上發表評論，或者聯繫我跟進。

Answer 2

一種選擇是將所有有效的英文單詞存儲在trie中。一旦你完成了這個任務，你就可以開始從根部向下走行，跟在字符串中的字母之後。無論何時你發現被標記爲一個字一個節點，你有兩個選擇：

1. 把輸入在這一點上，或
2. 繼續延伸的話。

您可以聲稱，如果您已將輸入分成一系列合法且沒有剩餘字符的單詞，即可找到匹配項。由於每封信都有一個強制選項（要麼建立一個無效的單詞，而應該停止 - 或 - 你可以繼續擴展單詞）或兩個選項（分開或繼續），你可以實現這個功能通過詳盡的遞歸：

PartitionWords(lettersLeft, wordSoFar, wordBreaks, trieNode): 
    // If you walked off the trie, this path fails. 
    if trieNode is null, return. 

    // If this trie node is a word, consider what happens if you split 
    // the word here. 
    if trieNode.isWord: 
     // If there is no input left, you're done and have a partition. 
     if lettersLeft is empty, output wordBreaks + wordSoFar and return 

     // Otherwise, try splitting here. 
     PartitinWords(lettersLeft, "", wordBreaks + wordSoFar, trie root) 

    // Otherwise, consume the next letter and continue: 
    PartitionWords(lettersLeft.substring(1), wordSoFar + lettersLeft[0], 
        wordBreaks, trieNode.child[lettersLeft[0]) 

在病理最壞的情況下會列出字符串，它可以T成倍長的所有分區。但是，只有當您可以用大量的方式對字符串進行分區時纔會出現這種情況，所有這些方式都以有效的英語單詞開始，並且在實踐中不太可能發生。如果字符串有很多分區，我們可能會花費很多時間來查找它們。例如，考慮字符串「dotheredo」。我們可以分成這麼多的方法：

do the redo 
do the red o 
doth ere do 
dot here do 
dot he red o 
dot he redo 

爲了避免這種情況，你可能要提起你報答案的數目，也許是兩個或三個的限制。

由於我們在離開trie時切斷了遞歸，如果我們嘗試了一個不會使字符串的剩餘部分有效的分割，我們將很快檢測到它。

希望這會有所幫助！

Answer 3

This link將這個問題描述爲一個完美的面試問題，並提供了幾種解決方法。基本上它涉及recursive backtracking。在這個級別上它會產生O（2^n）的複雜度。使用記憶的有效解決方案可能會將此問題降至O（n^2）。

Answer 4

import java.util。*;

class Position { 
    int indexTest,no; 
    Position(int indexTest,int no) 
    { 
     this.indexTest=indexTest; 
     this.no=no; 
    } } class RandomWordCombo { 
    static boolean isCombo(String[] dict,String test) 
    { 
     HashMap<String,ArrayList<String>> dic=new HashMap<String,ArrayList<String>>(); 
     Stack<Position> pos=new Stack<Position>(); 
     for(String each:dict) 
     { 
      if(dic.containsKey(""+each.charAt(0))) 
      { 
       //System.out.println("=========it is here"); 
       ArrayList<String> temp=dic.get(""+each.charAt(0)); 
       temp.add(each); 
       dic.put(""+each.charAt(0),temp); 
      } 
      else 
      { 
       ArrayList<String> temp=new ArrayList<String>(); 
       temp.add(each); 
       dic.put(""+each.charAt(0),temp); 
      } 
     } 
     Iterator it = dic.entrySet().iterator(); 
    while (it.hasNext()) { 
     Map.Entry pair = (Map.Entry)it.next(); 
     System.out.println("key: "+pair.getKey()); 
     for(String str:(ArrayList<String>)pair.getValue()) 
     { 
      System.out.print(str); 
     } 
    } 
     pos.push(new Position(0,0)); 
     while(!pos.isEmpty()) 
     { 
      Position position=pos.pop(); 
      System.out.println("position index: "+position.indexTest+" no: "+position.no); 
      if(dic.containsKey(""+test.charAt(position.indexTest))) 
      { 
       ArrayList<String> strings=dic.get(""+test.charAt(position.indexTest)); 
       if(strings.size()>1&&position.no<strings.size()-1) 
        pos.push(new Position(position.indexTest,position.no+1)); 
       String str=strings.get(position.no); 
       if(position.indexTest+str.length()==test.length()) 
        return true; 
       pos.push(new Position(position.indexTest+str.length(),0)); 
      } 
     } 
     return false; 
    } 
    public static void main(String[] st) 
    { 
     String[] dic={"world","hello","super","hell"}; 
     System.out.println("is 'hellworld' a combo: "+isCombo(dic,"superman")); 
    } } 

我已經做了類似的問題。如果給定的字符串是字典單詞的組合，這個解決方案給出了真或假。它可以很容易地轉換爲獲取空格分隔的字符串。它的平均複雜度是O（n），其中n：給定字符串中的字典單詞的數量。

Answer 5

使用Python，我們可以寫兩個功能，如果沒有這樣的分割是發現segment返回一塊連續文本中的所述第一分割成給定字典或None字的第一個。另一個功能segment_all返回找到的所有分段列表。最壞情況下的複雜度是O（n ** 2），其中n是字符中的輸入字符串長度。

此處介紹的解決方案可以擴展爲包括拼寫更正和雙字符分析以確定最可能的分段。

def memo(func): 
    ''' 
    Applies simple memoization to a function 
    ''' 
    cache = {} 
    def closure(*args): 
     if args in cache: 
      v = cache[args] 
     else: 
      v = func(*args) 
      cache[args] = v 
     return v 
    return closure 


def segment(text, words): 
    ''' 
    Return the first match that is the segmentation of 'text' into words 
    ''' 
    @memo 
    def _segment(text): 
     if text in words: return text 
     for i in xrange(1, len(text)): 
      prefix, suffix = text[:i], text[i:] 
      segmented_suffix = _segment(suffix) 
      if prefix in words and segmented_suffix: 
       return '%s %s' % (prefix, segmented_suffix) 
     return None 
    return _segment(text) 


def segment_all(text, words): 
    ''' 
    Return a full list of matches that are the segmentation of 'text' into words 
    ''' 
    @memo 
    def _segment(text): 
     matches = [] 
     if text in words: 
      matches.append(text) 
     for i in xrange(1, len(text)): 
      prefix, suffix = text[:i], text[i:] 
      segmented_suffix_matches = _segment(suffix) 
      if prefix in words and len(segmented_suffix_matches): 
       for match in segmented_suffix_matches: 
        matches.append('%s %s' % (prefix, match)) 
     return matches 
    return _segment(text) 


if __name__ == "__main__":  
    string = 'cargocultscience' 
    words = set('car cargo go cult science'.split()) 
    print segment(string, words) 
    # >>> car go cult science 
    print segment_all(string, words) 
    # >>> ['car go cult science', 'cargo cult science']