# 10 / 12

Given a list of strings 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.

"abcd" and "aacd" differ only by one

Input: dict = ["abcd","acbd", "aacd"]
Output: true

preprocess dict ["abcd","abcd", "aacd"]
-> set -> no duplicates ["abcd", "aacd"]

"abcd" -> "_bcd" "a_cd" "ab_d" "abc_"

"aacd" -> "_acd" "a_cd"
^^^^ match

def findOneDistanceString(strArr):
    
    # preprocess strArr
    
    strArr = set(strArr) #["abcd","abcd", "aacd"] -> ["abcd", "aacd"]
    
    possibilities = set() # a_cd
    
    def val(c):
        return ord(s[i] - 'a')
    # O(M(len of string arr)x N(lenth of string) x N(concate string))

    # loop str until find one distance str
    for s in strArr:
        hashOfS = 0
        base = 26
        for i in range(len(s)):
            hashOfS += hashOfS*base + val(s[i]))
        # a b c d
        # hashOfS = 26^3*a + 26^2*b + 26^1*c + d

        # _ b c d
        # hash = 0 + 26^2*b + 26^1*c + d
        
        # a _ c d
        # hash = 26^3*a + 0 + 26^1*c + d
        mul = 1
        for i in range(len(s)-1, -1, -1):
            # generate new possibilites
            # "abcd" -> "_bcd" "a_cd" "ab_d"  "abc_" 
            tmp = hashOfS - val(s[i])*mul
            # iter 1: hashOfS - s[-1] * 1
            # iter 2: hashOfS - s[-2] * 1*26
            # iter 3: hashOfS - s[-3] * 1*26*26
            mul *= base
            if tmp in possibilities:
                return True
            possibilities.add(tmp)
    
    
    # not Found
    return False


    # _ a -> 0    + 1
    
    # a _ -> 26*1 + 0