472. 連接詞
題目要理解起來不難，重點在于怎么判斷一個字串是否可以由其他的幾個字串組成，
既然是由其他的字串組成的，那么肯定是由比它更短的幾個組成的，這里用一個\(set\)記錄所有的單詞，主要是為了防止由空串這種特例，因為不能由自己來構成自己，
剩下來的步驟就是判斷是否可以由\(set\)里的單詞來組成自身，如果可以則加入結果中，
判斷的程序如下：
- 如果集合里沒有單詞或者是這個單詞本身就是空串，那么肯定無法組成這個單詞；
- 構造\(dp\)陣列，\(dp[i]\)的含義為\(word[0,i)\)之間的子串是否可以分解為在\(set\)中的單詞，\(dp[n]\)就代表是否可以完全分解；
- 那么就可以根據如上判斷\(word[0,i]\)是否可以分解為\(set\)中的較短單詞，先將上式分為\(word[0,j-1]\)和\(word[j,i]\)，前者對應了\(dp[j]\)，后者則為\(word[j,i]\)，只需判斷\(set\)是否包含有\(word[j,i]\)即可，如果包含則\(dp[i]=true\)；
- 回傳\(dp[word.length()]\)
class Solution {
public List<String> findAllConcatenatedWordsInADict(String[] words) {
List<String> ans = new ArrayList<>();
int n = words.length;
if(n < 3) {
return ans;
}
Set<String> set = new HashSet<>(Arrays.asList(words));
for(int i = 0; i < n; i++) {
// 去重空串
if("".equals(words[i])) {
continue;
}
// 先去重本身,后面再加回來
set.remove(words[i]);
if(canBreak(words[i], set)) {
ans.add(words[i]);
}
set.add(words[i]);
}
return ans;
}
// 判斷word是否可由set中的單詞組合而成
private boolean canBreak(String word, Set<String> set) {
int len = word.length();
// 如果單詞長度為0或者是集合為空了,那么肯定無法組成這個單詞
if(len == 0 || set.size() == 0) {
return false;
}
boolean[] dp = new boolean[len + 1];
dp[0] = true;
for(int i = 1; i < len + 1; i++) {
for(int j = 0; j < i; j++) {
// 如果無法構成word[0, j- 1]之間跳過
if(!dp[j]) {
continue;
}
if(set.contains(word.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[len];
}
}
除了上述的\(dp+set\)做法，還可以利用字典樹來減少前綴的匹配程序，這樣對于每個單詞，就不要遍歷完所有的字符，
我們可以先把單詞陣列按照長度從小到大排序，這樣就可以邊檢測邊判斷是否有連接詞，因為連接詞是由其他單詞組成的，所以它的長度肯定更長，在后面才做匹配程序，如果不是連接詞再把它加入到字典樹中去，
class Solution {
// 定義trie
private static class TrieNode {
boolean isWord;
Map<Character, TrieNode> children;
TrieNode() {
this.isWord = false;
this.children = new HashMap<>();
}
}
// 將單詞插入到字典樹中
private void insert(String word) {
char[] letters = word.toCharArray();
TrieNode curr = root;
for(char letter : letters) {
if(curr.children.get(letter) == null) {
curr.children.put(letter, new TrieNode());
}
curr = curr.children.get(letter);
}
curr.isWord = true;
}
// 字典樹的根節點
TrieNode root = new TrieNode();
public List<String> findAllConcatenatedWordsInADict(String[] words) {
List<String> ans = new ArrayList<>();
Arrays.sort(words, (a, b) -> a.length() - b.length());
for(String word : words) {
if(!word.isBlank()) {
// 可以由字典樹中的單詞組成則回傳結果
if(dfs(word, 0)) {
ans.add(word);
} else {
// 不是連接詞的則插入字典樹中
insert(word);
}
}
}
return ans;
}
private boolean dfs(String word, int position) {
if(position == word.length()) {
return true;
}
TrieNode curr = this.root;
while(position < word.length()) {
// 字典樹中不存在該字符
if(curr.children.get(word.charAt(position)) == null) {
return false;
}
curr = curr.children.get(word.charAt(position));
// 如果形成了一個完整的單詞,則進入下一層尋找是否可繼續組成
if(curr.isWord && dfs(word, position + 1)) {
return true;
}
position++;
}
return false;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/396031.html
標籤：Java