# 1554. Strings Differ by One Character

## Approach 1: BFS-like (TLE)

• Time: $O(nm^2)$
• Space: $O(nm)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: bool differByOne(vector& dict) { unordered_set seen; for (string& word : dict) { for (char& c : word) { const char cache = c; for (char next = 'a'; next <= 'z'; ++next) { if (next == cache) continue; c = next; if (seen.count(word)) return true; } c = cache; } seen.insert(word); } return false; } }; 

## Approach 2: Rabin-Karp

• Time: $O(nm) \to O(nm^2)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 class Solution { public: bool differByOne(vector& dict) { const int m = dict[0].length(); vector wordToHash; for (const string& word : dict) wordToHash.push_back(getHash(word)); // Compute the hash without each letter. // e.g. hash of "abc" = 26^2 * 'a' + 26 * 'b' + 'c' // newHash of "a*c" = hash - 26 * 'b' int coefficient = 1; for (int j = m - 1; j >= 0; --j) { unordered_map> newHashToIndices; for (int i = 0; i < dict.size(); ++i) { const string& word = dict[i]; const int newHash = (wordToHash[i] - static_cast(coefficient) * val(word[j]) % kMod + kMod) % kMod; if (const auto it = newHashToIndices.find(newHash); it != newHashToIndices.cend()) for (const int index : it->second) // word[0..j) == dict[index][0..j) && // word[j + 1..n) == dict[index][j + 1..n) if (equal(word.begin(), word.begin() + j, dict[index].begin()) && equal(word.begin() + j + 1, word.end(), dict[index].begin() + j + 1)) return true; newHashToIndices[newHash].push_back(i); } coefficient = 26L * coefficient % kMod; } return false; } private: static constexpr int kMod = 1'000'000'007; // Returns the hash of s. Assume the length of s is m. // e.g. getHash(s) = 26^(m - 1) * s[0] + 26^(m - 2) * s[1] + ... + s[m - 1]. int getHash(const string& s) { int hash = 0; for (const char c : s) hash = (26L * hash + val(c)) % kMod; return hash; } constexpr int val(char c) { return c - 'a'; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 class Solution { public boolean differByOne(String[] dict) { final int m = dict[0].length(); int[] wordToHash = new int[dict.length]; for (int i = 0; i < dict.length; ++i) wordToHash[i] = getHash(dict[i]); // Compute the hash without each letter. // e.g. hash of "abc" = 26^2 * 'a' + 26 * 'b' + 'c' // newHash of "a*c" = hash - 26 * 'b' int coefficient = 1; for (int j = m - 1; j >= 0; --j) { Map> newHashToIndices = new HashMap<>(); for (int i = 0; i < dict.length; ++i) { final int newHash = (int) ((wordToHash[i] - (long) coefficient * val(dict[i].charAt(j)) % kMod + kMod) % kMod); if (newHashToIndices.containsKey(newHash)) { for (final int index : newHashToIndices.get(newHash)) { if (dict[i].substring(0, j).equals(dict[index].substring(0, j)) && dict[i].substring(j + 1).equals(dict[index].substring(j + 1))) { return true; } } } newHashToIndices.putIfAbsent(newHash, new ArrayList<>()); newHashToIndices.get(newHash).add(i); } coefficient = (int) ((26L * coefficient) % kMod); } return false; } private static final int kMod = 1_000_000_007; // Returns the hash of s. Assume the length of s is m. // e.g. getHash(s) = 26^(m - 1) * s[0] + 26^(m - 2) * s[1] + ... + s[m - 1]. private int getHash(String s) { int hash = 0; for (final char c : s.toCharArray()) { hash = (int) ((26L * hash + val(c)) % kMod); } return hash; } private int val(char c) { return c - 'a'; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution: def differByOne(self, dict: List[str]) -> bool: kMod = 1_000_000_007 m = len(dict[0]) def val(c: str) -> int: return ord(c) - ord('a') def getHash(s: str) -> int: """Returns the hash of s. Assume the length of s is m. e.g. getHash(s) = 26^(m - 1) * s[0] + 26^(m - 2) * s[1] + ... + s[m - 1]. """ hash = 0 for c in s: hash = (26 * hash + val(c)) return hash wordToHash = [getHash(word) for word in dict] # Compute the hash without each letter. # e.g. hash of "abc" = 26^2 * 'a' + 26 * 'b' + 'c' # newHash of "a*c" = hash - 26 * 'b' coefficient = 1 for j in range(m - 1, -1, -1): newHashToIndices = collections.defaultdict(list) for i, (word, hash) in enumerate(zip(dict, wordToHash)): newHash = (hash - coefficient * val(word[j]) % kMod + kMod) % kMod if any(word[:j] == dict[index][:j] and word[j + 1:] == dict[index][j + 1:] for index in newHashToIndices[newHash]): return True newHashToIndices[newHash].append(i) coefficient = (26 * coefficient) % kMod return False