Given a list of strings?dict?where all the strings are of the same length.
Return?true?if there are 2 strings that only differ by 1 character in the same index, otherwise return?false.
Example 1:
Input: dict = ["abcd","acbd", "aacd"] Output: true Explanation: Strings "abcd" and "aacd" differ only by one character in the index 1.
Example 2:
Input: dict = ["ab","cd","yz"] Output: false
Example 3:
Input: dict = ["abcd","cccc","abyd","abab"] Output: true
Constraints:
- The number of characters in?
dict <= 105 dict[i].length == dict[j].lengthdict[i]?should be unique.dict[i]?contains only lowercase English letters.
思路：就是把word放进trie里面，然后用dfs去search，看有没有diff是1的word，分两种情况一种是c - 'a' == i; 一种是c - 'a' != i;?
class Solution {
class TrieNode {
public TrieNode[] children;
public boolean isword;
public String word;
public TrieNode() {
this.children = new TrieNode[26];
this.isword = false;
this.word = null;
}
}
class Trie {
private TrieNode root;
public Trie() {
this.root = new TrieNode();
}
public void insertWord(String word) {
TrieNode cur = this.root;
for(int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if(cur.children[c - 'a'] == null) {
cur.children[c - 'a'] = new TrieNode();
}
cur = cur.children[c - 'a'];
}
cur.isword = true;
cur.word = word;
}
}
public boolean differByOne(String[] dict) {
Trie trie = new Trie();
for(String word: dict) {
trie.insertWord(word);
}
for(String word: dict) {
if(search(trie.root, word, 0, 0)) {
return true;
}
}
return false;
}
public boolean search(TrieNode root, String word, int index, int diff) {
if(diff > 1) {
return false;
}
if(index == word.length() ) {
// 注意这里是root.isword 同时diff == 1;
return root.isword && diff == 1;
}
char c = word.charAt(index);
for(int i = 0; i < 26; i++) {
if(root.children[i] != null) {
if( c - 'a' == i) {
if(search(root.children[i], word, index + 1, diff)) {
return true;
}
} else {
// c - 'a' != i;
if(search(root.children[i], word, index + 1, diff + 1)) {
return true;
}
}
}
}
return false;
}
}
