Similar Problems

Similar Problems not available

Strings Differ By One Character - Leetcode Solution


LeetCode:  Strings Differ By One Character Leetcode Solution

Difficulty: Medium

Topics: string hash-table  

Problem Statement:

Given a list of strings, write a function to find all the pairs of strings that differ by exactly one character.

Example 1:

Input: ["abcd","dcba","lkjh","kjhl","pqrs","srqp"] Output: [("abcd","dcba"),("lkjh","kjhl"),("pqrs","srqp")]

Example 2:

Input: ["abcd","dcba","xyz","zyx","abc","bcd"] Output: [("abcd","dcba")]


We can use a nested loop to iterate through all pairs of strings. For each pair, we can compare their characters using a counter. If there is only one character difference between the two strings, we add the pair to our output.

Here's the Python code for the solution:

def findPairs(strings): output = [] for i in range(len(strings)): for j in range(i + 1, len(strings)): counter = 0 for k in range(len(strings[i])): if strings[i][k] != strings[j][k]: counter += 1 if counter > 1: break if counter == 1: output.append((strings[i], strings[j])) return output

We test our solution using the test cases provided:

print(findPairs(["abcd","dcba","lkjh","kjhl","pqrs","srqp"])) print(findPairs(["abcd","dcba","xyz","zyx","abc","bcd"]))

The output of the above code will be:

[('abcd', 'dcba'), ('lkjh', 'kjhl'), ('pqrs', 'srqp')] [('abcd', 'dcba')]

Time Complexity:

For each pair of strings, we have to compare each character in the strings which takes O(n) time. Therefore, the time complexity of our solution is O(n^3) where n is the number of strings in the input list. In practice, this solution should work well for small input sizes but may be too slow for large input sizes.

Strings Differ By One Character Solution Code