Open Zheaoli opened 2 years ago
class Solution {
Trie root = new Trie();
public List<String> findAllConcatenatedWordsInADict(String[] words) {
Arrays.sort(words, (a, b) -> a.length() - b.length());
List<String> res = new LinkedList<>();
for (String word : words) {
if (word.equals("")) {
continue;
}
if (dfs(word, 0)) {
res.add(word);
}
else {
insert(word);
}
}
return res;
}
private boolean dfs(String word, int start) {
if (start == word.length()) {
return true;
}
Trie curNode = root;
while (start < word.length()) {
if (curNode.children[word.charAt(start) - 'a'] == null) {
return false;
}
curNode = curNode.children[word.charAt(start) - 'a'];
if (curNode.isEnd && dfs(word, start + 1)) {
return true;
}
start++;
}
return false;
}
private void insert(String word) {
Trie curNode = root;
for (char c : word.toCharArray()) {
if (curNode.children[c - 'a'] == null) {
curNode.children[c - 'a'] = new Trie();
}
curNode = curNode.children[c - 'a'];
}
curNode.isEnd = true;
}
class Trie {
Trie[] children;
boolean isEnd;
public Trie() {
children = new Trie[26];
isEnd = false;
}
}
}
/*
* @lc app=leetcode.cn id=472 lang=typescript
*
* [472] 连接词
*/
// @lc code=start
function findAllConcatenatedWordsInADict(words: string[]): string[] {
class Node {
value: string
isEnd: boolean
children: Node[]
constructor(char: string) {
this.value = char
this.isEnd = false
this.children = Array(26).fill(null)
}
insertChar(char: string) {
const { children } = this
const index = char.charCodeAt(0) - 'a'.charCodeAt(0)
if (!children[index]) {
children[index] = new Node(char)
}
return children[index]
}
insert(str: string) {
let head = null
for (const char of str) {
head = (head || this).insertChar(char)
}
head.isEnd = true
}
}
function checkValid(root: Node, str: string) {
const len = str.length
let head = root
let l = 0
while (head && l < len) {
const index = str[l++].charCodeAt(0) - 'a'.charCodeAt(0)
head = head.children[index]
if (head && head.isEnd && l < len && checkValid(root, str.substring(l))) {
return true
}
if (head && head.isEnd && l === len) {
return true
}
}
return false
}
const newWords = words.filter(word => word !== '')
newWords.sort((a, b) => a.length - b.length)
const root = new Node('')
const res = []
for (const word of newWords) {
if (checkValid(root, word)) {
res.push(word)
} else {
root.insert(word)
}
}
return res
};
// @lc code=end
2021-12-28