Suppose we have a list of lowercase strings called words where each word is of the same length. We have to check whether there are two strings that differ only in one character.
So, if the input is like words = ["seed", "pick", "lick", "root", "live"], then the output will be True, as "pick" and "lick" are almost same.
To solve this, we will follow these steps −
- s := a new set
- for each word in words, do
- for each index i and word w in word, do
- if substring of word[from index 0 to i - 1] concatenate "*" concatenate word[from index i + 1 to end] is present in s, then
- return True
- otherwise,
- insert (word[from index 0 to i-1] concatenate "*" concatenate word[from index i + 1 to end]) into s
- if substring of word[from index 0 to i - 1] concatenate "*" concatenate word[from index i + 1 to end] is present in s, then
- for each index i and word w in word, do
- return False
Example
Let us see the following implementation to get a better understanding−
def solve(words):
s = set()
for word in words:
for i, w in enumerate(word):
if word[:i] + "*" + word[i + 1 :] in s:
return True
else:
s.add(word[:i] + "*" + word[i + 1 :])
return False
words = ["seed", "pick", "lick", "root", "live"]
print(solve(words))
Input
["seed", "pick", "lick", "root", "live"]
Output
True
No comments:
Post a Comment