74일 (2451. Odd String Difference) String

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.

 

- 접근방법

 

소문자 영문자는 int로 97~122(a~z)로 표시된다.

각 문자를 정수로 변환하였을때의 차이를 word.length()-1의 배열로 표시하면 된다.

 

예시를 보면 빠르다.

ex) "adc"라면 'a'와 'd'와 'c'로 구성된다.

(int) 'a' = 97,  (int) 'd' = 100,  (int) 'c' = 99이다.

(100 - 97), (99 - 100) = [3,-1]이다.

즉 "adc"는 {3, -1}로 표현된다.

 

이렇게 문자열이 각각의 일차원배열로 표현될때, 배열 내부의 값이 같지않은 하나의 일차원배열을 이루는 원래 문자열을 찾아서 리턴하면 된다.

 

 

- 코드

class Solution {
    public String oddString(String[] words) {
        int n = words[0].length(); // 0
        int[] arr1 = new int[n];
        int ptr = 0;
        int cnt = 0;

        for (int j = 0; j + 1 < n; j++) { // 1
            arr1[j] += words[0].charAt(j + 1) - words[0].charAt(j);
        }

        for (int i = 1; i < words.length; i++) {
            int[] arr2 = new int[words[0].length()]; // 2

            for (int j = 0; j + 1 < n; j++) { // 3
                arr2[j] += words[i].charAt(j + 1) - words[i].charAt(j);
            }

            if (Arrays.equals(arr1, arr2)) cnt++; // 4
            else ptr = i;
        }

        return cnt == 0 ? words[0] : words[ptr]; // 5
    }
}

 

 

0. 사용할 변수들을 초기화

 

1~3. arr1 = words[0] 그리고 arr2 = words[1] ~ words[words.length]이다.

arr1과 각각의 모든 arr2를 비교하기 위함이다.

 

4~5 . arr1이 중복된다면 cnt != 0d이 된다.. 이경우 arr1은 정답에서 제외되며,

arr1과 각각의 arr2와 비교시 arr2가 다른 경우가 단 한번 있을텐데 이때 arr2의 원래 문자열이 정답이 된다.

(cnt > 0이므로 arr1은 정답이 아니라고 판명되었는데 arr1 != arr2라면 arr2가 정답)

 

arr1이 중복되지않고 cnt == 0이라면 arr1이 유일한 수이므로 arr1의 원래 문자열 words[0]을 리턴하면 된다.

 

 

 

https://leetcode.com/problems/odd-string-difference/

Odd String Difference - LeetCode