检查相同字母间的距离

难度: 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 中出现，可以忽略。
因为 s 是一个匀整字符串，返回 true 。

示例 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

Submission

运行时间: 22 ms

内存: 16.1 MB

class Solution:
    def checkDistances(self, s: str, distance: List[int]) -> bool:
        last = [0] * 26
        for i, c in enumerate(s):
            c = ord(c) - ord('a')
            if last[c] and i - last[c] != distance[c]:
                return False
            last[c] = i + 1
        return True

Explain

此题解的核心思路是使用一个数组来记录每个字符最后一次出现的位置，数组的索引表示字符（从'a'到'z'映射到0到25），数组的值表示该字符最后一次出现的位置加1。遍历字符串s中的每个字符，利用其ASCII值减去'a'的ASCII值得到字符对应的索引。若该字符之前已出现过（即last数组对应位置非0），则计算当前位置与上一次出现位置之间的距离，并与distance数组中的值进行比较，如果不相等则直接返回False。若遍历完毕没有发现不符合条件的情况，则返回True。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def checkDistances(self, s: str, distance: List[int]) -> bool:
        last = [0] * 26  # 初始化记录每个字符最后出现位置的数组
        for i, c in enumerate(s):  # 遍历字符串中的每个字符及其索引
            c_index = ord(c) - ord('a')  # 计算字符对应的索引
            if last[c_index]:  # 如果该字符之前已出现过
                if i - last[c_index] != distance[c_index]:  # 检查当前字符的间距是否符合预期
                    return False  # 如果不符合预期，返回False
            last[c_index] = i + 1  # 更新该字符的最后出现位置
        return True  # 如果所有字符都符合预期的间距，返回True

Explore

在算法中，使用数组last来记录每个字符最后一次出现的位置加1（而不是直接记录位置），是为了初始化数组时使用0值来表示该字符尚未出现。如果数组直接记录字符的位置，那么初始化值0将无法区分字符在首位出现和字符未出现的情况。通过记录位置加1，我们可以利用0值表示未出现，而其他非零值减1即可得到实际的字符位置。这种处理方式简化了逻辑并避免了额外的判断。

在检查间距是否符合预期时，使用的比较方式if i - last[c_index] != distance[c_index]是因为这种方式直接反映了字符之间的实际距离与预设距离的对比。这里的last[c_index]记录的是字符上次出现位置的下一个位置，所以i - last[c_index]正好计算出两次出现之间的距离（即索引之差）。如果这个计算出的距离与distance数组中对应的预期距离不一致，表示字符串中的字符间距不满足题目要求，因此这是一种直接且有效的比较方式。

如果distance数组中某个字符对应的值为0，理论上这意味着这个字符在字符串中不应连续出现。根据题目的算法逻辑，当该字符再次出现时，会计算与其上次出现位置的距离，如果计算结果不为0，则会返回False。因此，如果预设的距离为0，而该字符在字符串中再次出现，算法将直接返回False，表示字符串不符合给定的距离要求。

是的，如果last数组直接记录字符的位置，那么初始化值为0将无法区分字符首次出现和索引为0的情况。这正是为何last数组记录的是每个字符最后一次出现的位置加1。这样，初始化为0表示字符尚未出现，而任何非零值减1后可以得到实际的字符位置。这种方法有效地解决了首次出现与索引为0的情况之间的区分问题。