Easy

题目描述

给你一个下标从 0 开始的字符串 s ，该字符串仅由小写英文字母组成，其中 s 中的每个字母都 恰好 出现 两次 。另给你一个下标从 0 开始、长度为 26 的的整数数组 distance 。

字母表中的每个字母按从 0 到 25 编号（即，'a' -> 0, 'b' -> 1, 'c' -> 2, … , 'z' -> 25）。

在一个 间距合适 的字符串中，第 i 个字母的两次出现之间的字母数量是 distance[i] 。如果第 i 个字母没有在 s 中出现，那么 distance[i] 可以 忽略 。

如果 s 是一个 间距合适 的字符串，返回 true ；否则，返回 false 。

示例 1：

输入：s = "abaccb", distance = [1,3,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
输出：true
解释：
- 'a' 出现在下标 0 和 2 处，满足 distance[0] = 1 。
- 'b' 出现在下标 1 和 5 处，满足 distance[1] = 3 。
- 'c' 出现在下标 3 和 4 处，满足 distance[2] = 0 。
注意 distance[3] = 5，但是由于 'd' 没有在 s 中出现，可以忽略。
返回 true ，因为 s 是一个间距合适的字符串。

示例 2：

输入：s = "aa", distance = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
输出：false
解释：
- 'a' 出现在下标 0 和 1 处，所以它们之间距离为 0 。
但是 distance[0] = 1 ，所以 s 不是一个间距合适的字符串。

提示：

  • 2 <= s.length <= 52
  • s 只包含小写英文字母
  • s 中每个字母恰好出现两次
  • distance.length == 26
  • 0 <= distance[i] <= 50

解题思路

这道题的核心是理解"距离"的定义：两个相同字母之间的字母数量，而不是索引差值。

解题思路：

  1. 记录第一次出现位置：遍历字符串，用数组记录每个字母第一次出现的位置。
  2. 计算距离并验证：当遇到某个字母的第二次出现时，计算实际距离并与期望距离比较。
  3. 距离计算公式：如果字母在位置 i 和 j 出现（i < j），则它们之间的字母数量为 j - i - 1。

算法流程：

  • 初始化长度为26的数组记录每个字母的第一次出现位置，初始值设为-1表示未出现
  • 遍历字符串：
    • 如果当前字母第一次出现，记录其位置
    • 如果是第二次出现，计算实际距离 当前位置 - 第一次位置 - 1
    • 将实际距离与 distance 数组中的期望值比较，不匹配则返回false
  • 所有字母都验证通过则返回true

时间复杂度O(n)，空间复杂度O(1)（固定大小的数组）。

代码实现

class Solution {
public:
    bool checkDistances(string s, vector<int>& distance) {
        vector<int> firstPos(26, -1);
        
        for (int i = 0; i < s.length(); i++) {
            int charIndex = s[i] - 'a';
            
            if (firstPos[charIndex] == -1) {
                firstPos[charIndex] = i;
            } else {
                int actualDistance = i - firstPos[charIndex] - 1;
                if (actualDistance != distance[charIndex]) {
                    return false;
                }
            }
        }
        
        return true;
    }
};

class Solution:
    def checkDistances(self, s: str, distance: List[int]) -> bool:
        first_pos = [-1] * 26
        
        for i, char in enumerate(s):
            char_index = ord(char) - ord('a')
            
            if first_pos[char_index] == -1:
                first_pos[char_index] = i
            else:
                actual_distance = i - first_pos[char_index] - 1
                if actual_distance != distance[char_index]:
                    return False
        
        return True

public class Solution {
    public bool CheckDistances(string s, int[] distance) {
        int[] firstPos = new int[26];
        Array.Fill(firstPos, -1);
        
        for (int i = 0; i < s.Length; i++) {
            int charIndex = s[i] - 'a';
            
            if (firstPos[charIndex] == -1) {
                firstPos[charIndex] = i;
            } else {
                int actualDistance = i - firstPos[charIndex] - 1;
                if (actualDistance != distance[charIndex]) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

var checkDistances = function(s, distance) {
    const firstPos = new Array(26).fill(-1);
    
    for (let i = 0; i < s.length; i++) {
        const charIndex = s.charCodeAt(i) - 97; // 'a'.charCodeAt(0) = 97
        
        if (firstPos[charIndex]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次，n为字符串长度
空间复杂度O(1)使用固定大小的数组（26个字母）

相关题目