差值数组不同的字符串【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，否则返回0int 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];}
  }
  

  • 复杂度
    • 时间复杂度：$\mathcal{O}(m\ast n)$，n为字符串长度，m为字符串个数
    • 空间复杂度：$\mathcal{O}(n)$

纵向比较实现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）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。