Content

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

Constraints:

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and wordDict[i] consist of only lowercase English letters.
All the strings of wordDict are unique.

Solution

1. 字典树 + DFS

Java

class Solution {
    DictNode head = new DictNode('\u0000');
    public boolean wordBreak(String s, List<String> wordDict) {
        // 1 <= s.length <= 300
        // 1 <= wordDict.length <= 1000
        // 1 <= wordDict[i].length <= 20
        // s and wordDict[i] consist of only lowercase English letters.
        // All the strings of wordDict are unique.
        List<String> filteredWordDict = wordDict.stream()
                .filter(o -> o.length() <= s.length())
                .sorted(Comparator.comparingInt(String::length))
                .collect(Collectors.toList());
        List<String> newWordDict = new ArrayList<>();
        for (int i = 0; i < filteredWordDict.size(); i++) {
            String word0 = filteredWordDict.get(i);
            int len0 = word0.length();
            if (len0 > s.length()) {
                continue;
            }
            boolean ignore = false;
            for (int j = i + 1; j < filteredWordDict.size(); j++) {
                String word1 = filteredWordDict.get(j);
                int len1 = word1.length();
                if (len1 <= s.length() && !word1.equals(word0) && len1 / len0 > 1 && len1 % len0 == 0) {
                    int i0 = 0;
                    int j0 = 0;
                    while (j0 < len1) {
                        if (word1.charAt(j0) != word0.charAt(i0 % len0)) {
                            break;
                        }
                        i0++;
                        j0++;
                    }
                    if (j0 >= len1) {
                        ignore = true;
                        break;
                    }
                }
            }
            if (!ignore) {
                newWordDict.add(word0);
            }
        }
        // 初始化字典树
        DictNode dictNode;
        boolean[] hash = new boolean[26];
        for (String word : newWordDict) {
            dictNode = head;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                int j = c - 'a';
                if (null == dictNode.children[j]) {
                    dictNode.children[j] = new DictNode(c);
                    hash[j] = true;
                }
                dictNode = dictNode.children[j];
            }
            dictNode.word = word;
        }
        for (int i = 0; i < s.length(); i++) {
            if (!hash[s.charAt(i) - 'a']) {
                return false;
            }
        }
        return dfs(s, 0, head);
    }
    private boolean dfs(String s, int i, DictNode node) {
        if (i >= s.length()) {
            return node == head;
        }
        int j = s.charAt(i) - 'a';
        DictNode child = node.children[j];
        if (null == child) {
            return false;
        } else if (null != child.word) {
            return dfs(s, i + 1, head) || dfs(s, i + 1, child);
        } else {
            return dfs(s, i + 1, child);
        }
    }
}
class DictNode {
    char c;
    DictNode[] children;
    String word;
    public DictNode(char c) {
        this.c = c;
        children = new DictNode[26];
        word = null;
    }
}

2. 动态规划

Java

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 1 <= s.length <= 300
        // 1 <= wordDict.length <= 1000
        // 1 <= wordDict[i].length <= 20
        // s and wordDict[i] consist of only lowercase English letters.
        // All the strings of wordDict are unique.
        Map<Integer, Set<String>> words = new TreeMap<>(Comparator.naturalOrder());
        for (String word : wordDict) {
            words.computeIfAbsent(word.length(), i -> new HashSet<>()).add(word);
        }
        int n = s.length();
        // dp[i]表示包括左端点长度为i的子串是否符合要求
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (Map.Entry<Integer, Set<String>> entry : words.entrySet()) {
                Integer wordLen = entry.getKey();
                Set<String> hash = entry.getValue();
                int j = i - wordLen;
                dp[i] = j >= 0 && dp[j] && hash.contains(s.substring(j, i));
                if (j < 0 || dp[i]) {
                    break;
                }
            }
        }
        return dp[n];
    }
}