Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given s = “leetcode”, dict = [“leet”, “code”].
Return true because “leetcode” can be segmented as “leet code”.
O(n^2) or O(n^3) time O(n) space DP solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
publicclassSolution{ publicbooleanwordBreak(String s, Set<String> wordDict){ if (s == null || wordDict.size() == 0) returnfalse; boolean[] breaks = newboolean[s.length() + 1]; breaks[0] = true; // empty string should be true for (int i = 1; i <= s.length(); i++) { for (int j = 0; j < i; j++) { if (breaks[j] && wordDict.contains(s.substring(j, i))) { breaks[i] = true; // we only care if this position can be broken, but don't care about how it should be break break; } } } return breaks[s.length()]; } }
publicbooleanwordBreak(String s, Set<String> dict){ if (dict.contains(s)) returntrue; Queue<Integer> queue = new LinkedList<Integer>(); queue.offer(0); // use a set to record checked index to avoid repeated work. // This is the key to reduce the running time to O(N^2). Set<Integer> visited = new HashSet<Integer>(); visited.add(0); while (!queue.isEmpty()) { int curIdx = queue.poll(); for (int i = curIdx+1; i <= s.length(); i++) { if (visited.contains(i)) continue; if (dict.contains(s.substring(curIdx, i))) { if (i == s.length()) returntrue; queue.offer(i); visited.add(i); } } } returnfalse; }