Teaching Kids Programming: Videos on Data Structures and Algorithms
You are given a list of lowercase alphabet strings words where each string is of the same length. Return whether there’s two strings that differ only in one index.
Constraints
1 ≤ n ≤ 100,000 where n is the total number of characters in words
Example 1
Input
words = [“abcd”, “aaaa”, “abcf”]
Output
True
Explanation
We see that “abcd” and “abcf” only differ in the last index.
Almost Same String Algorithm via Hash Set
We can iterate each word and push all its variants by one character (replaced by ‘*’) into the hash set. The time complexity is O(NL) where there are N words and each word has L characters. And space complexity is also O(NL).
1 2 3 4 5 6 7 8 9 10 | class Solution: def solve(self, words): data = set() for w in words: for i in range(len(w)): t = w[:i] + "*" + w[i+1:] if t in data: return True data.add(t) return False |
class Solution: def solve(self, words): data = set() for w in words: for i in range(len(w)): t = w[:i] + "*" + w[i+1:] if t in data: return True data.add(t) return False
If we go with the bruteforce, this would take O(LN^2) – bruteforce each pair and check if two words diff in one index.
See also: Hash Algorithm to Check A List Containing Almost Same Strings (Differ By One Character)
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Compute the Account Voting Power (Mana) for Accounts on Steem Blockchain using Javascript/NodeJs Function
Next Post: A Simple PHP Function to Disable Google Fonts in WordPress