Description

Submission

class Solution {
public:
    bool differByOne(vector<string>& dict) {
        vector<uint64_t> hashes;
        const uint64_t base = 26;
        const int n = dict.size();
        const int m = dict[0].size();

        for(auto& s: dict) {
            uint64_t hash = 0;
            for(auto ch: s) {
                hash = hash * base + (ch - 'a');
            }
            hashes.push_back(hash);
        }

        uint64_t coeff = 1;
        for(int i = m-1; i >= 0; --i) {
            unordered_set<uint64_t> newHashes;
            
            for(int j = 0; j < n; ++j) {
                uint64_t newHash = hashes[j] - (dict[j][i] - 'a') * coeff;
                if(newHashes.count(newHash)) return true;
                newHashes.insert(newHash);
            }

            coeff *= base;
        }

        return false;
    }
};