[LeetCode] Odd String Difference

아르당·2026년 9월 11일

LeetCode

목록 보기
520/602
post-thumbnail

문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

길이가 같은 문자열 배열 words가 주어진다. 각 문자열의 길이를 n이라고 가정한다.
각 문자열 words[i]는 길이 n - 1인 차이 정수 배열 difference[i]로 변환될 수 있고, difference[i][j] = words[i][j + 1] - words[i][j]이고 0 <= j <= n - 2이다. 두 문자의 차이는 알파벳 내에서의 위치 차이를 의미한다.

  • 예를 들어, 문자열 "acb"에 대해 차이 정수 배열은 [2 - 0, 1 - 2] = [2, -1]이다.

wods에서 모든 문자열은 하나를 제외하고 같은 차이 정수 배열을 가진다. 해당 문자열을 찾아야 한다.
다른 차이 정수 배열을 가진 문자열을 반환해라.

Example

#1
Input: words = ["adc", "wzy", "abc"]
Output: "abc"
Explanation:

  • "adc"의 차이 정수 배열은 [3 - 0, 2 - 3] = [3, -1]이다.
  • "wzy"의 차이 정수 배열은 [25 - 22, 24 - 25] = [3, -1]이다.
  • "abc"의 차이 정수 배열은 [1 - 0, 2 - 1] = [1, 1]이다.

조건에 맞지 않는 배열은 [1, 1]이라서, 해당 문자열 "abc"를 반환한다.

#2
Input: words = ["aaa", "bob", "ccc", "ddd"]
Output: "bob"
Explanation: 모든 정수 배열은 "bob"를 제외하고 [0, 0]이고, [13, -13]이 해당한다.

Constraints

  • 3 <= words.length <= 100
  • n == words[i].length
  • 2 <= n <= 20
  • words[i]는 영어 소문자로 구성된다.

Solved

class Solution {
    public String oddString(String[] words) {
        Map<List<Integer>, Integer> map1 = new HashMap<>();
        Map<String, List<Integer>> map2 = new HashMap<>();

        for(int i = 0; i < words.length; i++){
            List<Integer> diff = indexDiff(words[i]);
            map2.put(words[i], diff);
            map1.put(diff, map1.getOrDefault(diff, 0) + 1);
        }

        for(String key: map2.keySet()){
            if(map1.get(map2.get(key)) == 1){
                return key;
            }
        }

        return "";
    }

    private List<Integer> indexDiff(String s){
        List<Integer> list = new ArrayList<>();

        for(int i = 1; i < s.length(); i++){
            list.add((s.charAt(i) - 'a') - (s.charAt(i - 1) - 'a'));
        }

        return list;
    }
}
profile
내 마음대로 코드 작성하는 세상

0개의 댓글