leetcode：139. 单词拆分（字典树法+剪枝）3ms

淩亂°似流年 2021-09-28 11:22 298阅读 0赞

给定一个**非空**字符串 *s* 和一个包含**非空**单词列表的字典 *wordDict*，判定 *s* 是否可以被空格拆分为一个或多个在字典中出现的单词。

**说明：**

*  拆分时可以重复使用字典中的单词。
 *  你可以假设字典中没有重复的单词。

**示例 1：**

输入: s = "leetcode", wordDict = ["leet", "code"]
    输出: true
    解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

**示例 2：**

输入: s = "applepenapple", wordDict = ["apple", "pen"]
    输出: true
    解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
         注意你可以重复使用字典中的单词。

**示例 3：**

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
    输出: false

package LeetCode;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class WordBreak139 {
        TrieNode root;
    
        public WordBreak139() {
            root = new TrieNode();
        }
        //把单词加入到字典树中
        public void insert(String w) {
            TrieNode r = root;
            for (int i = 0; i < w.length(); i++) {
                int index = w.charAt(i) - 'a';
                if (r.childs[index] == null) {
                    r.childs[index] = new TrieNode();
                }
                r = r.childs[index];
            }
            r.isWord = true;
        }
    
        public boolean wordBreak(String s, List<String> wordDict) {
            //把每个lise中单词加入到字典树中
            for (int i = 0; i < wordDict.size(); i++) {
                String ws = wordDict.get(i);
                insert(ws);
            }
            //用来记录上个单词结束（或者说记录下一个字典中词的开始位置）第一个位置是入口所以设为true
            boolean[] juge = new boolean[s.length() + 1];
            juge[0] = true;
            //
            for (int i = 0; i < s.length(); i++) {
                //要在记录的字典树中所包含了的后面一个开始也就是前一个字典已找出没必要在所属字中找另一个字
                if (juge[i] == true) {
                    //每次搜索初始化字典开始
                    TrieNode r = root;
                    //字典树的搜索
                    for (int j = i; j < s.length(); j++) {
                         int index =s.charAt(j) - 'a';
                         //判断是否字符在字典树中（判断字符是否为字典中的字或者是字典中的前缀）
                        //如果不是前缀或者不是字典中的词则直接结束循环
                        if (r != null && r.childs[index] != null) {
                            r = r.childs[index];
                            if (r.isWord) {
                                juge[j + 1] = true;
                            }
                        } else {
                            break;
                        }
                    }
                }
            }
            return juge[s.length()];
        }
    
        public static void main(String[] args) {
            WordBreak139 w = new WordBreak139();
            List<String> strings = new ArrayList<>();
            strings.add("leet");
            strings.add("code");
            w.wordBreak("leetcode", strings);
        }
    }