【每日一题Day217】LC2451差值数组不同的字符串

这篇具有很好参考价值的文章主要介绍了【每日一题Day217】LC2451差值数组不同的字符串 | 枚举+变量记录。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

差值数组不同的字符串【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。

实现文章来源地址https://www.toymoban.com/news/detail-466221.html

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];
    }
}

复杂度
- 时间复杂度： $\mathcal{O}(m*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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。