- 题目描述
- 解题思路
- 代码(前缀树 + dfs + 记忆化)
力扣链接 题目描述
给你一个字符串 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
提示:
- 1 <= s.length <= 300
- 1 <= wordDict.length <= 1000
- 1 <= wordDict[i].length <= 20
- s 和 wordDict[i] 仅有小写英文字母组成
- wordDict 中的所有字符串 互不相同
官方题解
- 前缀树 + dfs + 记忆化
class Solution { TrieNode root = new TrieNode(null); //记录已经递归过的索引,这里必须要使用数组来记录递归过的索引,不然会出现超时,重复的太多 boolean[] index = new boolean[301]; public boolean wordBreak(String s, ListwordDict) { //构建前缀树 for (String word : wordDict) { insert(word); } //查询 return dfs(s, 0); } boolean dfs(String s, int cur) { //cur越界,说明遍历完成,返回true if (cur == s.length()) { return true; } //从index数组可以直接判断当前索引是否已经遍历过,遍历过说明该索引不能成功,直接返回false; if (index[cur]) { return false; } //记忆当前索引被遍历过,置index[cur] = true index[cur] = true; TrieNode temp = root; for (int i = cur; i < s.length(); i++) { char c = s.charAt(i); TrieNode trieNode = temp.children.get(c); if (trieNode == null) { return false; } if (trieNode.isEnd) { if (dfs(s, i + 1)) { return true; } } temp = trieNode; } return false; } //将一个word插入到字典树中 public void insert(String word) { int n = word.length(); TrieNode temp = root; for (int i = 0; i < n; i++) { char c = word.charAt(i); TrieNode node = temp.children.get(c); if (node == null) { node = new TrieNode(c); temp.children.put(c, node); } temp = node; } temp.isEnd = true; } //字典树节点 class TrieNode { Character c; Map children; boolean isEnd; TrieNode(Character c) { children = new HashMap<>(); this.c = c; } } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)