leetcode
leetcode 2051 ~ 2100
检查相同字母间的距离

检查相同字母间的距离

难度:

标签:

题目描述

代码结果

运行时间: 22 ms, 内存: 16.1 MB


/*
 * 思路:
 * 1. 使用Java Stream API处理字符串s。
 * 2. 利用map记录字母第一次出现的索引。
 * 3. 遍历字符串s,对已出现的字符计算两次出现之间的距离并与distance数组中的对应值比较。
 * 4. 如果所有字符的计算距离都满足要求,返回true,否则返回false。
 */

import java.util.*;
import java.util.stream.*;

public class Solution {
    public boolean checkDistances(String s, int[] distance) {
        Map<Character, Integer> firstOccurrence = new HashMap<>();
        return IntStream.range(0, s.length()).allMatch(i -> {
            char c = s.charAt(i);
            return firstOccurrence.merge(c, i, (prev, curr) -> {
                if (curr - prev - 1 == distance[c - 'a']) {
                    return curr;
                } else {
                    throw new RuntimeException();
                }
            }) == i || true;
        });
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在算法中,为何选择数组last来记录每个字符最后一次出现的位置加1,而不是直接记录位置?
在算法中,使用数组last来记录每个字符最后一次出现的位置加1(而不是直接记录位置),是为了初始化数组时使用0值来表示该字符尚未出现。如果数组直接记录字符的位置,那么初始化值0将无法区分字符在首位出现和字符未出现的情况。通过记录位置加1,我们可以利用0值表示未出现,而其他非零值减1即可得到实际的字符位置。这种处理方式简化了逻辑并避免了额外的判断。
🦆
为什么在检查间距是否符合预期时,使用的是if i - last[c_index] != distance[c_index]而不是其他比较方式?
在检查间距是否符合预期时,使用的比较方式if i - last[c_index] != distance[c_index]是因为这种方式直接反映了字符之间的实际距离与预设距离的对比。这里的last[c_index]记录的是字符上次出现位置的下一个位置,所以i - last[c_index]正好计算出两次出现之间的距离(即索引之差)。如果这个计算出的距离与distance数组中对应的预期距离不一致,表示字符串中的字符间距不满足题目要求,因此这是一种直接且有效的比较方式。
🦆
算法中提到如果字符之前已出现过,则会进行距离比较,如果这个字符在distance数组中对应的值为0怎么处理?
如果distance数组中某个字符对应的值为0,理论上这意味着这个字符在字符串中不应连续出现。根据题目的算法逻辑,当该字符再次出现时,会计算与其上次出现位置的距离,如果计算结果不为0,则会返回False。因此,如果预设的距离为0,而该字符在字符串中再次出现,算法将直接返回False,表示字符串不符合给定的距离要求。
🦆
在遍历字符串的过程中,last数组的初始化值为0,这是否意味着无法区分字符首次出现和索引为0的情况?如果是,如何解决这个问题?
是的,如果last数组直接记录字符的位置,那么初始化值为0将无法区分字符首次出现和索引为0的情况。这正是为何last数组记录的是每个字符最后一次出现的位置加1。这样,初始化为0表示字符尚未出现,而任何非零值减1后可以得到实际的字符位置。这种方法有效地解决了首次出现与索引为0的情况之间的区分问题。

相关问题