[LeetCode - Biweekly Contest 90] 2451. Odd String Difference

2451. Odd String Difference

Easy

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

Each string words[i] can be converted into a difference integer array difference[i] of length n - 1 where difference[i][j] = words[i][j+1] - words[i][j] where 0 <= j <= n - 2. Note that the difference between two letters is the difference between their positions in the alphabet i.e. the position of 'a' is 0, 'b' is 1, and 'z' is 25.

• For example, for the string "acb", the difference integer array is [2 - 0, 1 - 2] = [2, -1].

All the strings in words have the same difference integer array, except one. You should find that string.

Return the string in words that has different difference integer array.

 

Example 1:

Input: words = ["adc","wzy","abc"]
Output: "abc"
Explanation: 
- The difference integer array of "adc" is [3 - 0, 2 - 3] = [3, -1].
- The difference integer array of "wzy" is [25 - 22, 24 - 25]= [3, -1].
- The difference integer array of "abc" is [1 - 0, 2 - 1] = [1, 1]. 
The odd array out is [1, 1], so we return the corresponding string, "abc".

Example 2:

Input: words = ["aaa","bob","ccc","ddd"]
Output: "bob"
Explanation: All the integer arrays are [0, 0] except for "bob", which corresponds to [13, -13].

 

Constraints:

• 3 <= words.length <= 100
• n == words[i].length
• 2 <= n <= 20
• words[i] consists of lowercase English letters.

---

문제 풀이

• 주어진 단어들 중에 단어의 알파벳 값을 순서대로 계산했을때의 차이 값이 단어 하나만 제외하고 모두 같다. 
• 차이 값을 계산하는 방법은 뒤에있는 알파벳의 아스키코드 값에 현재 위치의 알파벳의 아스키코드를 빼는 것이다. 
• 예를 들어 'adc'가 있으면 아스키코드 값은 032인데 이 것을 차이 값으로 만들면 [3 - 0, 2 - 3]이 된다. 
• 제한 사항을 보면 단어의 총 개수가 최악의 경우 100개이기 때문에 시간 복잡도 상관없이 풀어도된다.
• dictionary를 두개를 만들고, 각 단어들의 차이 값 배열에 대한 개수를 첫번째 딕셔너리에서 세어준다.
• 그리고  두번째 딕셔너리에 차이 값 배열을 키로 넣고, 벨류 값으로 단어를 넣는다.
• 그리고 마지막에 벨류값이 1인 단어를 반환한다.

소스 코드

class Solution:
    def oddString(self, words: List[str]) -> str:
        d = defaultdict(int)
        d2 = dict()
        for i in range(0, len(words)):
            cur = []
            for j in range(1, len(words[i])):
                cur.append((ord(words[i][j]) - ord('a')) - (ord(words[i][j - 1]) - ord('a')))
            cur = tuple(cur)
            d[cur] += 1
            d2[cur] = words[i]
        for k, v in d.items():
            if v == 1:
                return d2[k]