Google : 句子分割

回复  wwwyhx
类似这样：can[ i ]代表从头开始共i个字符能否被分割。内存循环其实可以到maxL也就是字典中单词的最大长度就退出，所以复杂度可以到O(maxL*n)。
darksteel 发表于 2011-7-16 02:53

    很好,谢谢,我那个递归的的确存在大量重复计算

也贴上我的回朔@@

1. import java.util.LinkedList;
   
2. 
   
3. public class Sentence {
   
4.     public static void main(String[] args) {
   
5.         String[] dic = {"a", "apply", "back", "i", "is", "isasen", "sentence", "this", "tence"};
   
6.         String sentence = "thisisasentence";
   
7.         splitSentence(sentence, dic);
   
8.     }
   
9. 
   
10.     public static void splitSentence(String sentence, String[] dic) {
    
11.         int index = 0;
    
12.         boolean valid = true;
    
13.         StringBuffer buffer = new StringBuffer();
    
14.         LinkedList<String> wordstack = new LinkedList<String>();
    
15.         LinkedList<Integer> indexstack = new LinkedList<Integer>();
    
16.         
    
17.         while (true) {
    
18.             if (index == sentence.length()) {                    //BACKTRACK
    
19.                 if(indexstack.isEmpty()) break;                   //EXIT
    
20.                 buffer = new StringBuffer();
    
21.                 buffer.append(wordstack.removeLast());
    
22.                 index = indexstack.removeLast() + 1;
    
23.                 continue;
    
24.             }
    
25.             String str = buffer.append(sentence.charAt(index)).toString();            if (isWord(str, dic)) {
    
26.                 wordstack.add(str);
    
27.                 buffer = new StringBuffer();
    
28.                 indexstack.add(index);
    
29.                 valid = true;
    
30.             } else { valid = false; }
    
31.             index++;
    
32.             if (index == sentence.length() && valid)             //PRINT
    
33.                 System.out.println("solution: " + wordstack);
    
34.         }
    
35.     }
    
36. 
    
37.     public static boolean isWord(String word, String[] dic) {
    
38.         for (int i=0; i<dic.length; i++)
    
39.             if(word.equals(dic[i]))
    
40.                 return true;
    
41.         return false;
    
42.     }
    
43. }
    

复制代码