Leetcode 1554 Strings Differ by One Character

Problem statement

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

Solution

One idea is for each word abcd create words #bcd, a#cd, ab#d, abc# and put them to set.

Complexity

Time and space complexity is O(n*m^2).

Code

class Solution:
    def differByOne(self, dct):
        n, m = len(dct), len(dct[0])
        cnt = set()
        for word in dct:
            for i in range(m):
                cand = word[:i] + "#" + word[i+1:]
                if cand in cnt: return True
                cnt.add(cand)
                
        return False

Remark

There is also O(nm) in average time complexity solution, if we use rolling hashes. The idea is to calculate hashes for each string and then for each of m possible hashes check if we have 1) pair of strings which differ by element with index 0. 2) pair of strings which differ by element with index 1 and so on.