1554

1554. Strings Differ by One Character (Medium)

Given a list of strings dict where all the strings are of the same length.

Return True if there are 2 strings that only differ by 1 character in the same index, otherwise return False.

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.

 

Example 1:

Input: dict = ["abcd","acbd", "aacd"]
Output: true
Explanation: Strings "abcd" and "aacd" differ only by one character in the index 1.

Example 2:

Input: dict = ["ab","cd","yz"]
Output: false

Example 3:

Input: dict = ["abcd","cccc","abyd","abab"]
Output: true

 

Constraints:

• Number of characters in dict <= 10^5
• dict[i].length == dict[j].length
• dict[i] should be unique.
• dict[i] contains only lowercase English letters.

Companies:
Airbnb

Related Topics:
Hash Table, String, Rolling Hash, Hash Function

Solution 1. Set

// OJ: https://leetcode.com/problems/strings-differ-by-one-character/
// Author: github.com/lzl124631x
// Time: O(NM^2)
// Space: O(N)
class Solution {
public:
    bool differByOne(vector<string>& A) {
        unordered_set<string> s(begin(A), end(A));
        for (auto str : s) {
            for (int i = 0; i < str.size(); ++i) {
                char c = str[i];
                for (int j = 0; j < 26; ++j) {
                    if (c == 'a' + j) continue;
                    str[i] = 'a' + j;
                    if (s.count(str)) return true;
                }
                str[i] = c;
            }
        }
        return false;
    }
};

Solution 2. Rabin Karp

// OJ: https://leetcode.com/problems/strings-differ-by-one-character/
// Author: github.com/lzl124631x
// Time: O(NM)
// Space: O(N)
class Solution {
    typedef unsigned long long ULL;
public:
    bool differByOne(vector<string>& A) {
        ULL d = 16777619, p = 1, N = A.size(), M = A[0].size();
        vector<ULL> h(N);
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                h[i] = h[i] * d + A[i][j];
            }
        }
        for (int i = M - 1; i >= 0; --i, p *= d) {
            unordered_set<ULL> s;
            for (int j = 0; j < N; ++j) {
                ULL n = h[j] - A[j][i] * p;
                if (s.count(n)) return true;
                s.insert(n);
            }
        }
        return false;
    }
};