【Leetcode】1554. Strings Differ by One Character

题目地址：

https://leetcode.com/problems/strings-differ-by-one-character/description/

给定$m$个长度都是$n$的字符串，问是否存在两个字符串只在一个位置上不同。

思路是字符串哈希。先将所有的字符串的哈希值加入一个哈希表中，接着遍历每个字符串，枚举这个字符串的$n$个位置，看一下将当前位置替换为字符$0$（意思是ASCII码为$0$的字符）的时候的哈希值是否存在过，如果存在，则说明最终答案是存在（因为这说明某两个字符串将某个位置同时变为$0$的时候，哈希值就相等了）。代码如下：

class Solution {
 public:
  using UL = unsigned long;
  bool differByOne(vector<string>& dict) {
    UL P = 131;
    if (dict.empty()) return false;
    int n = dict[0].size();
    UL pow[n];
    memset(pow, 0, sizeof pow);
    pow[0] = 1;
    for (int i = 1; i < n; i++) pow[i] = pow[i - 1] * P;
    vector<UL> ha;
    for (int i = 0; i < dict.size(); i++) {
      UL hash = 0;
      for (int j = 0; j < n; j++) hash = hash * P + dict[i][j];
      ha.push_back(hash);
    }

    unordered_set<UL> st;
    for (int i = 0; i < dict.size(); i++) {
      UL hash = ha[i];
      vector<UL> v;
      for (int j = 0; j < n; j++) {
        UL new_ha = hash - pow[n - 1 - j] * dict[i][j];
        if (st.count(new_ha)) return true;
        v.push_back(new_ha);
      }

      st.insert(v.begin(), v.end());
    }

    return false;
  }
};
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

时空复杂度$O(mn)$。