差值数组不同的字符串【LC2451】
给你一个字符串数组
words，每一个字符串长度都相同，令所有字符串的长度都为n。每个字符串
words[i]可以被转化为一个长度为n - 1的差值整数数组difference[i]，其中对于0 <= j <= n - 2有difference[i][j] = words[i][j+1] - words[i][j]。注意两个字母的差值定义为它们在字母表中 位置 之差，也就是说'a'的位置是0，'b'的位置是1，'z'的位置是25。
- 比方说，字符串
"acb"的差值整数数组是[2 - 0, 1 - 2] = [2, -1]。
words中所有字符串 除了一个字符串以外 ，其他字符串的差值整数数组都相同。
你需要找到那个不同的字符串。
请你返回 words中 差值整数数组 不同的字符串。
纵向比较实现1
- 思路
由于words中所有字符串 除了一个字符串以外 ，其他字符串的差值整数数组都相同。因此我们可以求出第一个字符串的差值数组，并记录该差值数组出现的次数count。然后枚举其他字符串，比较差值数组是否相同，分情况讨论。 - 如果差值数组不同，并且
count>1，那么此时的字符串即为答案。
- 但是，还存在一种情况，第一个字符串为答案，那么最终
count一直为1。
- 实现
class Solution { public String oddString(String[] words) { // 先记录第一个字符串的差值数组，并记录该差值数组出现的次数count // 再记录与它不同的差值数组的下标diff // 最后如果count>1，那么返回diff，否则返回0 int n = words[0].length(); int[] array = new int[n - 1]; int count = 1, index = -1; for (int i = 0; i < n - 1; i++){ array[i] = words[0].charAt(i + 1) - words[0].charAt(i); } for (int j = 1; j < words.length; j++){ boolean same = true; for (int i = 0; i < n - 1; i++){ if (words[j].charAt(i + 1) - words[j].charAt(i) != array[i]){ same = false; index = j; break; } } if (same) count++; if (count > 1 && index != -1) return words[index]; } return words[0]; } }
纵向比较实现2
- 思路：
也是先记录第一个字符串的差值数组，然后找到与它不同的字符串，那么答案幸福二选一。再选择另一个字符串与第一个字符串的差值数组进行比较，如果不同，答案为第一个字符串，反之为另一个字符串 - 实现
class Solution { public String oddString(String[] words) { int n = words.length; int i = 1; for(i = 1; i < n; i++){ if(!check(words[i], words[0])){ break; } } for(int j = 1; j < n; j++){ if(j != i){ if(check(words[j], words[0])){ return words[i]; } else{ return words[0]; } } } return ""; } private boolean check(String s1, String s2){ int n = s1.length(); int m = s1.charAt(0) - s2.charAt(0); for(int i = 1; i < n; i++){ if(s1.charAt(i) - s2.charAt(i) != m){ return false; } } return true; } } 作者：一只粗糙的疯子 链接：https://leetcode.cn/problems/odd-string-difference/solutions/2282834/chai-zhi-shu-zu-bu-tong-de-zi-fu-chuan-b-siph/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
