Odd String Difference — LeetCode 2451 Python Solution

The problem

You are given an array of equal-length strings words. Assume that the length of each string is n.

Example

Input

words = ["adc","wzy","abc"]

Output

"abc"

Explanation

- The difference integer array of "adc" is [3 - 0, 2 - 3] = [3, -1].

Python solution

class Solution:
    def oddString(self, words: List[str]) -> str:
        d = defaultdict(list)
        for s in words:
            t = tuple(ord(b) - ord(a) for a, b in pairwise(s))
            d[t].append(s)
        return next(ss[0] for ss in d.values() if len(ss) == 1)

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 2451. Odd String Difference is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems