首页 > 代码库 > Problem Word Break II

Problem Word Break II

Problem Description:

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

 

 Solution:
 1 public List<String> wordBreak(String s, Set<String> dict) { 2         Set<Character> set = new HashSet<Character>(); 3         for (int i = 0; i < s.length(); i++) { 4             set.add(s.charAt(i)); 5         } 6         for (char a : set) { 7             boolean found = false; 8             for (String word : dict) { 9                 if (word.indexOf((int)a) >= 0) {10                     found = true;11                 }12             }13 14             if (! found) {15                 return new ArrayList<String>();16             }17         }18 19 20         List<String> list = new ArrayList<String>();21         if (s == null || dict == null || dict.size() == 0) {22             return new ArrayList<String>();23         }24         if (s.equals("")) {25             list.add("");26             return list;27         }28         boolean match = false;29         for (String word : dict) {30             if (word.length() <= s.length()) {31                 if (s.substring(0, word.length()).equals(word)) {32                     match = true;33                     List<String> others = wordBreak(s.substring(word.length()), dict);34                         for (String other : others) {35                             if (! other.equals("")) {36                               list.add(word.concat(" ").concat(other));37                             } else {38                                 list.add(word);39                             }40                         }41                 }42             }43         }44 45 46         return match ? list : new ArrayList<String>();47     }