公众号merlinsea
- 链接：
https://leetcode.cn/problems/word-break/description/
- 题目描述：
- 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
- 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
- 解题思路1: dfs求解
- c++版本：
class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { if(s.size()>135){ return false; } bool r = dfs(s,wordDict); return r; } // andog // ["cats", "dog", "sand", "and", "cat"] bool dfs(string s,vector<string>& wordDict){ if(s==""){ return true; } // 我们匹配了很多没有意义的单词 for(int i=0;i<wordDict.size();i++){ string word = wordDict[i]; int j = 0; // 需要用word和s去匹配 while(j<word.size() && j<s.size() && s[j]==word[j]){ j++; } if(j==word.size()){ // 说明匹配成功 string newS = s.substr(j,s.size()-j); bool r = dfs(newS,wordDict); if(r){ return true; } } } return false; } };
- java版本：
class Solution { public boolean wordBreak(String s, List<String> wordDict) { if(s.length()>135){ return false; } return dfs(s,wordDict); } private boolean dfs(String s,List<String> wordDict){ if("".equals(s)){ return true; } for(int i=0;i<wordDict.size();i++){ String word = wordDict.get(i); if(word.length() > s.length()){ continue; } if(s.substring(0,word.length()).equals(word)){ String newS = s.substring(word.length()); boolean r = dfs(newS,wordDict); if(r){ return true; } } } return false; } }
- 解题思路2：前缀树将单词字典收敛以后再进行dfs
- 需要注意我们这里是通过边（即next）路径作为单词字母，而非节点作为单词字母。
- c++版本
struct Node{ vector<Node*> next; bool isWord; // true说明是单词结束 ，false 说明不是单词结束 Node(){ next.resize(26,nullptr); isWord = false; } }; class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { //例子中有一个特殊的情况，这个情况会超时 if(s.size()>150){ return false; } //1、我们需要构建出Node Node* root = createTrie(wordDict); // dfs bool r = dfs(s,root); return r; } bool dfs(string s, Node*& root){ if(s == ""){ // 匹配成功 return true; } Node* p = root; int i = 0; while(i<s.size() && p->next[s[i]-'a']!=nullptr){ p = p->next[s[i]-'a']; if(p->isWord){ string newS = s.substr(i+1); bool r = dfs(newS,root); if(r){ return true; } } i++; } // 一定匹配不上 return false; } Node* createTrie(vector<string>& wordDict){ // 为什么要先创建root， Node* root = new Node(); for(int i=0;i<wordDict.size();i++){ string word = wordDict[i]; // 需要把word插入到root里面去 insert(word,root); } return root; } void insert(string word,Node*& root){ Node* p = root; // 为什么i从0开始？ for(int i=0;i<word.size();i++){ char ch = word[i]; // ch代表下一个单词 // 思路难点？ if(p->next[ch-'a'] == nullptr){ p->next[ch-'a'] = new Node(); } p = p->next[ch-'a']; } // p是指向哪里？ p->isWord = true; } };
- java版本
class Node{ Node[] next; boolean isWord; Node(){ isWord = false; next = new Node[26]; } } class Solution { public boolean wordBreak(String s, List<String> wordDict) { if(s.length()>135){ return false; } Node root = createTrie(wordDict); return dfs(s,0,root); } private boolean dfs(String s,int i,Node root){ if(i>=s.length()){ return true; } Node p = root; while(i<s.length() && p.next[s.charAt(i)-'a']!=null){ p = p.next[s.charAt(i)-'a']; i++; if(p.isWord){ boolean r = dfs(s,i,root); if(r){ return true; } } } return false; } private Node createTrie(List<String> wordDict){ Node root = new Node(); for(String word : wordDict){ insert(word,root); } return root; } private void insert(String word,Node root){ Node p = root; for(int i=0;i<word.length();i++){ char ch = word.charAt(i); if(p.next[ch-'a']==null){ p.next[ch-'a'] = new Node(); } p = p.next[ch-'a']; } // 但for循环时候，p指向路径终点 p.isWord = true; } }
vip直播算法课教学详情如下：
奔跑的小梁，公众号：梁霖编程工具库leetcode刷题永久班直播教学，手把手带你刷题，价格调整通知，2022年11月14日
