1554. Strings Differ by One Character

1. naive

1.
BruteForce, check all pairs and verify if they differ in one character. 
O(n^2 * m) where n is the number of words and m is the length of each string.

class Solution {
    public boolean differByOne(String[] dict) {
        int n = dict.length;
        for (int i = 0; i < n ;i++) {
            for (int j = i+1; j < n; j++) {
                int count = 0;
                for (int w = 0 ; w < dict[i].length(); w++) {
                    if (dict[i].charAt(w) != dict[j].charAt(w)) {
                        count++;
                    }
                }
                if (count == 1) {
                    return true;
                }
            }
        }
        return false;
    }
}

2.use hashset

2.

T: O(m^2 * n), Use hashset, 
to insert all possible combinations adding a character "*". 

For example: If dict[i] = "abc", insert ("*bc", "a*c" and "ab*").
1 word, len m => generated m string, so m^2
n word => so n*m^2

S: O(m^2 * n)

class Solution {
    public boolean differByOne(String[] dict) {
        Set<String> seen = new HashSet<>();
        
        for (String w : dict) {
            char[] c = w.toCharArray();
            for (int i = 0; i < c.length; i++) {
                char temp = c[i];
                c[i] = '*';
                String changedStr = String.valueOf(c);
                if (seen.contains(changedStr)) {
                    return true;
                }
                seen.add(changedStr);
                c[i] = temp;
            }
        }
        return false;
    }
}
/*
1.
BruteForce, check all pairs and verify if they differ in one character. 
O(n^2 * m) where n is the number of words and m is the length of each string.

2.
O(m^2 * n), Use hashset, 
to insert all possible combinations adding a character "*". 

For example: If dict[i] = "abc", insert ("*bc", "a*c" and "ab*").
*/

Follow up: Could you solve this problem in O(n * m) where n is the length of dict and m is the length of each string.

using rolling hash, put string in hashset