Easy

题目描述

给你一个由若干长度相等的字符串组成的数组 words。假设每个字符串的长度为 n。

每个字符串 words[i] 可以转换为一个长度为 n - 1 的差值整数数组 difference[i]，其中 difference[i][j] = words[i][j+1] - words[i][j]，0 <= j <= n - 2。注意，两个字母之间的差值是它们在字母表中位置的差值，即 'a' 的位置是 0，'b' 的位置是 1，'z' 的位置是 25。

  • 例如，字符串 "acb" 的差值整数数组是 [2 - 0, 1 - 2] = [2, -1]。

words 中所有字符串除了一个字符串以外，其他字符串的差值整数数组都相同。你需要找到那个不同的字符串。

返回 words 中差值整数数组不同的字符串。

示例 1：

输入：words = ["adc","wzy","abc"]
输出："abc"
解释：
- "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：

输入：words = ["aaa","bob","ccc","ddd"]
输出："bob"
解释：所有字符串的整数数组都是 [0, 0]，只有 "bob" 对应 [13, -13]。

提示：

  • 3 <= words.length <= 100
  • n == words[i].length
  • 2 <= n <= 20
  • words[i] 仅由小写英文字母组成

解题思路

解题思路

这道题的核心是找到数组中唯一不同的差值数组对应的字符串。

基本思路：

  1. 为每个字符串计算差值数组
  2. 找出哪个差值数组与其他不同
  3. 返回对应的字符串

具体实现方法：

方法一：哈希表计数法

  • 计算每个字符串的差值数组，并用哈希表统计每种差值数组的出现次数
  • 出现次数为1的就是我们要找的异常字符串

方法二：前三个比较法（推荐）

  • 由于只有一个字符串不同，我们只需要比较前三个字符串的差值数组
  • 如果前两个相同，那么第三个要么相同（异常在后面），要么不同（第三个是异常）
  • 如果前两个不同，那么第一个和第三个比较，相同的那个是正常模式

由于题目保证有且仅有一个异常字符串，方法二更加高效，时间复杂度更低。

算法步骤：

  1. 计算前三个字符串的差值数组
  2. 通过比较确定正常的差值数组模式
  3. 遍历所有字符串，找到差值数组与正常模式不同的字符串

代码实现

class Solution {
public:
    string oddString(vector<string>& words) {
        auto getDiff = [](const string& word) {
            vector<int> diff;
            for (int i = 1; i < word.length(); i++) {
                diff.push_back(word[i] - word[i-1]);
            }
            return diff;
        };
        
        vector<int> diff0 = getDiff(words[0]);
        vector<int> diff1 = getDiff(words[1]);
        vector<int> diff2 = getDiff(words[2]);
        
        vector<int> normalDiff;
        int oddIndex = -1;
        
        if (diff0 == diff1) {
            normalDiff = diff0;
            if (diff2 != normalDiff) {
                oddIndex = 2;
            }
        } else if (diff0 == diff2) {
            normalDiff = diff0;
            oddIndex = 1;
        } else {
            normalDiff = diff1;
            oddIndex = 0;
        }
        
        if (oddIndex != -1) {
            return words[oddIndex];
        }
        
        for (int i = 3; i < words.size(); i++) {
            if (getDiff(words[i]) != normalDiff) {
                return words[i];
            }
        }
        
        return "";
    }
};

class Solution:
    def oddString(self, words: List[str]) -> str:
        def get_diff(word):
            return [ord(word[i]) - ord(word[i-1]) for i in range(1, len(word))]
        
        diff0 = get_diff(words[0])
        diff1 = get_diff(words[1])
        diff2 = get_diff(words[2])
        
        if diff0 == diff1:
            normal_diff = diff0
            if diff2 != normal_diff:
                return words[2]
        elif diff0 == diff2:
            normal_diff = diff0
            return words[1]
        else:
            normal_diff = diff1
            return words[0]
        
        for i in range(3, len(words)):
            if get_diff(words[i]) != normal_diff:
                return words[i]
        
        return ""

public class Solution {
    public string OddString(string[] words) {
        int[] GetDiff(string word) {
            int[] diff = new int[word.Length - 1];
            for (int i = 1; i < word.Length; i++) {
                diff[i - 1] = word[i] - word[i - 1];
            }
            return diff;
        }
        
        bool ArraysEqual(int[] arr1, int[] arr2) {
            if (arr1.Length != arr2.Length) return false;
            for (int i = 0; i < arr1.Length; i++) {
                if (arr1[i] != arr2[i]) return false;
            }
            return true;
        }
        
        int[] diff0 = GetDiff(words[0]);
        int[] diff1 = GetDiff(words[1]);
        int[] diff2 = GetDiff(words[2]);
        
        int[] normalDiff;
        int oddIndex = -1;
        
        if (ArraysEqual(diff0, diff1)) {
            normalDiff = diff0;
            if (!ArraysEqual(diff2, normalDiff)) {
                oddIndex = 2;
            }
        } else if (ArraysEqual(diff0, diff2)) {
            normalDiff = diff0;
            oddIndex = 1;
        } else {
            normalDiff = diff1;
            oddIndex = 0;
        }
        
        if (oddIndex != -1) {
            return words[oddIndex];
        }
        
        for (int i = 3; i < words.Length; i++) {
            if (!ArraysEqual(GetDiff(words[i]), normalDiff)) {
                return words[i];
            }
        }
        
        return "";
    }
}

var oddString = function(words) {
    const getDiff = (word) => {
        const diff = [];
        for (let i = 1; i < word.length; i++) {
            diff.push(word.charCodeAt(i) - word.charCodeAt(i - 1));
        }
        return diff;
    };
    
    const arraysEqual = (arr1, arr2) => {
        if (arr1.length !== arr2.length) return false;
        for (let i = 0; i < arr1.length; i++) {
            if (arr1[i] !== arr2[i]) return false;
        }
        return true;
    };
    
    const diff0 = getDiff(words[0]);
    const diff1 = getDiff(words[1]);
    const diff2 = getDiff(words[2]);
    
    let normalDiff;
    let oddIndex = -1;
    
    if (arraysEqual(diff0, diff1)) {
        normalDiff = diff0;
        if (!arraysEqual(diff2, normalDiff)) {
            oddIndex = 2;
        }
    } else if (arraysEqual(diff0, diff2)) {
        normalDiff = diff0;
        oddIndex = 1;
    } else {
        normalDiff = diff1;
        oddIndex = 0;
    }
    
    if (oddIndex !== -1) {
        return words[oddIndex];
    }
    
    for (let i = 3; i < words.length; i++) {
        if (!arraysEqual(getDiff(words[i]), normalDiff)) {
            return words[i];
        }
    }
    
    return "";
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型推荐解法
时间复杂度O(n × m)
空间复杂度O(m)

其中：

  • n 是字符串数组的长度
  • m 是单个字符串的长度

说明：需要为每个字符串计算差值数组（O(m)），最坏情况下需要检查所有字符串（O(n)），因此总时间复杂度为 O(n × m)。空间复杂度主要用于存储差值数组，为 O(m)。

相关题目