1554. Strings Differ by One Character

Approach 1: BFS-like (TLE)

• Time: $O(nm^2)$
• Space: $O(nm)$

C++

class Solution {
 public:
  bool differByOne(vector<string>& dict) {
    unordered_set<string> 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.contains(word))
            return true;
        }
        c = cache;
      }
      seen.insert(word);
    }

    return false;
  }
};

Approach 2: Rabin-Karp

• Time: $O(nm) \to O(nm^2)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  bool differByOne(vector<string>& dict) {
    const int m = dict[0].length();
    vector<int> 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<int, vector<int>> newHashToIndices;
      for (int i = 0; i < dict.size(); ++i) {
        const string& word = dict[i];
        const int newHash =
            (wordToHash[i] -
             static_cast<long>(coefficient) * val(word[j]) % kHash + kHash) %
            kHash;
        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 = coefficient * kBase % kHash;
    }

    return false;
  }

 private:
  static constexpr long kBase = 26;
  static constexpr int kHash = 1'000'000'007;

  static constexpr int val(char c) {
    return c - 'a';
  }

  // 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 = (hash * kBase + val(c)) % kHash;
    return hash;
  }
};

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<Integer, List<Integer>> newHashToIndices = new HashMap<>();
      for (int i = 0; i < dict.length; ++i) {
        final int newHash =
            (int) ((wordToHash[i] - (long) coefficient * val(dict[i].charAt(j)) % kHash + kHash) %
                   kHash);
        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) (coefficient * kBase % kHash);
    }

    return false;
  }

  private static final long kBase = 26;
  private static final int kHash = 1_000_000_007;

  private static int val(char c) {
    return c - 'a';
  }

  // 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) ((hash * kBase + val(c)) % kHash);
    }
    return hash;
  }
}

class Solution:
  def differByOne(self, dict: list[str]) -> bool:
    kBase = 26
    kHash = 1_000_000_007
    m = len(dict[0])

    def val(c: str) -> int:
      return string.ascii_lowercase.index(c)

    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 = (hash * kBase + 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]) % kHash + kHash) % kHash
        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 = coefficient * kBase % kHash

    return False