Pages

Program to check whether there is any pair of words which are almost same in Python

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
  • return False

Program to check whether there is any pair of words that are almost the same in Python
 

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


Top 5 jobs in Cloud Computing in IT Industry

TOP QUESTIONS TO ASK AN INTERVIEWEE

No comments:

Post a Comment