Teaching Kids Programming – Using Hash Set to Find Out Almost Same Strings


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) —

GD Star Rating
loading...
345 words
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

The Permanent URL is: Teaching Kids Programming – Using Hash Set to Find Out Almost Same Strings

Leave a Reply