# 1554. Strings Differ by One Character
###### tags: `Leetcode` `FaceBook` `Medium`
## 思路
### 思路一 $O(N * M^2)$ N是dict的长度 M是每个string的长度
和[0127. Word Ladder](https://hackmd.io/2F_Qo1tWSH2QKrMp6USYEw)思路有点像
把每个字符串的每个位置挖掉，然后放进set里面
**时间复杂度是因为 concatenation of two strings takes O(m1 + m2) time.**
### 思路二 Trie $O(M * N)$
### 思路三 String Hash $O(M * N)$
通过给字符串编码，再放进hashset里面，进而找重复的
这里的mod是实验试出来，理论上来说YOU CAN NOT AVOID COLLISION COMPLETELY.
如果第16行和第18行的回圈倒着写，且不加set.clear()就会出错，例如遇到aaade这个字符串第一次删第一个a，会产生aade，第二次删第二个a，还是会产生aade，就会出错，所以需要先遍历各个位置，再遍历每个字符串，每次换位置的时候把set清空

第一个思路不会遇到这个问题是因为用```*```标示除了到底是哪个字符被拿掉了
所以上面的case，会产生```*aade,a*ade,aa*de```

## Code
### 思路一

class Solution {
    public boolean differByOne(String[] dict) {
        Set<String> set = new HashSet<>();
        for(int i = 0;i < dict.length;i++){
            String str = dict[i];
            for(int j = 0;j < str.length();j++){
                String t = str.substring(0,j)+"*"+str.substring(j+1, str.length());
                if(set.contains(t)){
                    return true;
                }
                set.add(t);
            }
        }
        return false;
    }
}

### 思路二 Trie

class Solution {
    class TrieNode{
        TrieNode[] children = new TrieNode[26];
        boolean end = false;
    }
    TrieNode root;

    public boolean differByOne(String[] dict) {
        root = new TrieNode();
        int n = dict.length;
        for(int i=0; i<n; i++){
            add(dict[i]);
        }
        for(int i=0; i<n; i++){
            if(dfs(dict[i], 0, 0, root)) return true;
        }
        return false;
    }

    private void add(String s){
        TrieNode curr = root;
        for(int i=0; i<s.length(); i++){
            if(curr.children[s.charAt(i)-'a']==null) curr.children[s.charAt(i)-'a'] = new TrieNode();
            curr = curr.children[s.charAt(i)-'a'];
        }
        curr.end = true;
    }

    private boolean dfs(String s, int diff, int idx, TrieNode curr){
        if(curr==null) return false;
        if(idx>=s.length()){
            return diff==1 && curr.end;
        }
        if(diff>1) return false;
        for(int i=0; i<26; i++){
            if(curr.children[i]==null) continue;
            if(i==s.charAt(idx)-'a'){
                if(dfs(s, diff, idx+1, curr.children[i])) return true;
            } 
            else if(dfs(s, diff+1, idx+1, curr.children[i])) return true; 
        }
        return false;
    }
}

### 思路三 String Hash

class Solution {
    public boolean differByOne(String[] dict) {
        Set<Long> set = new HashSet<>();
        long mod = (long) Math.pow(10, 20) + 7;
        
        int len = dict[0].length();
        long[] word2hash = new long[dict.length];
        
        for(int i = 0;i < dict.length;i++){
            String str = dict[i];
            for(int j = 0;j < str.length();j++){
                word2hash[i] = (word2hash[i]*26 + (str.charAt(j)-'a'))%mod;
            }
        }
        long base = 1;
        for (int j = len - 1; j >= 0; j--) {
            set.clear();
            for (int i = 0; i < dict.length; i++) {
                long newHash = (word2hash[i] - base * (dict[i].charAt(j)-'a')) % mod;
                if (set.contains(newHash)) {
                    return true;
                }
                set.add(newHash);
            }
            base = 26 * base % mod;
        }
        return false;
    }
}