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 =
dict =
s =
"catsanddog"
,dict =
["cat", "cats", "and", "sand", "dog"]
.
A solution is
["cats and dog", "cat sand dog"]
.When the iteration detects "cat", it splits the string to prefix ="cat" and suffix = "sanddog". Take the suffix as the input, the method checks for the next prefix ("sand"). When it detects "dog", the input is in the dictionary, so we simply add the input into the result array (rst) and return.
"catsanddog" -> len == 3, "cat" + "sanddog" -> "sand" + "dog" -> "dog", add to the map and rst, return rst -> "sand" + " " + "dog" (from tmp), add to the map and rst, return rst -> "cat" + " " + "sand dog" = "cat sand dog", add to the map and rst;
"catsanddog" -> len == 4, "cats" + "anddog" -> "and" + "dog" -> "dog", get from map, return rst -> "and" + " " + "dog" -> "cats" + " " + "and dog" = "cats and dog", add to the map and rst, return rst;
public class Solution { public ArrayListwordBreak(String s, Set dict) { ArrayList rst = new ArrayList (); if (s == null || dict.isEmpty()) return rst; HashMap > map = new HashMap >(); rst = wordBreakHelper(s, dict, map); return rst; } private ArrayList wordBreakHelper(String s, Set dict, HashMap > map) { if (map.containsKey(s)) return map.get(s); ArrayList rst = new ArrayList (); int length = s.length(); if (length <= 0) return rst; for (int len = 1; len <= length; len++) { String prefix = s.substring(0, len); if (dict.contains(prefix)) { if (len == length) rst.add(prefix); else { String suffix = s.substring(len); ArrayList tmp = wordBreakHelper(suffix, dict, map); for (String items : tmp) { String words = prefix + " " + items; rst.add(words); } } } } map.put(s, rst); return rst; } }
No comments:
Post a Comment