public class Solution {

    private int maxWordLen;

    public List<String> wordBreak(String s, List<String> wordDict) {
        if (s == null || wordDict == null) {
            return null;
        }
        List<String> result = new ArrayList<>();
        maxWordLen = maxLen(wordDict);
        if (!canBreak(s, wordDict)) {
            return result;
        }
        helper(s, wordDict, 0, result, new StringBuilder());
        return result;
    }

    private boolean canBreak(String s, List<String> wordDict) {
        if (s == null || wordDict == null) {
            return false;
        }
        int len = s.length();
        boolean[] result = new boolean[len + 1];
        result[0] = true;
        for (int i = 1; i < len + 1; i++) {             for (int j = i - 1; j >= 0; j--) {
                if (i - j > maxWordLen) {
                    result[i] = false;
                    break;
                }
                if (result[j] && wordDict.contains(s.substring(j, i))) {
                    result[i] = true;
                    break;
                }
            }
            //result[i] = false; // Caused erro here. Must know the logic clearly,
            //should not add this line, or all the result field will be set to false.
        }
        return result[len];
    }

    private int maxLen(List<String> wordDict) {
        int result = 0;
        for (String word : wordDict) {
            int l = word.length();
            result = result > l ? result : l;
        }
        return result;
    }

    private void helper(String s, List<String> wordDict, int start, List<String> result, StringBuilder sb) {
        if (start == s.length()) {
            result.add(sb.substring(0, sb.length() - 1)); // -1 is needed to get rid of " " at the end.
            return;
        }
        // Should notice this. We need only one loop, because we are using recursion, so we only need to know
        // whether there exits a word started from "start". One loop is enough.
        for (int j = start + 1; j <= s.length(); j++) {             if (j - start > maxWordLen) {
                break;
            }
            if (wordDict.contains(s.substring(start, j))) {
                int len1 = sb.length();
                sb.append(s.substring(start, j) + " ");
                int len2 = sb.length();
                helper(s, wordDict, j, result, sb);
                sb.delete(len1, len2);
            }
        }
    }
}

http://lib.csdn.net/article/datastructure/16321

Advertisements