【LeeCode】2399. 检查相同字母间的距离

【题目描述】

给你一个下标从 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 。

 https://leetcode.cn/problems/check-distances-between-same-letters/

【示例】

【代码】LeeCode-枚举

package com.company;
import java.util.*;
// 2023-04-09

class Solution {
    public boolean checkDistances(String s, int[] distance) {
        int len = s.length();
        for (int i = 0; i < len; i++){
            for (int j = i + 1; j < len; j++){
                if (s.charAt(i) == s.charAt(j) && distance[s.charAt(i) - 'a'] != j - i - 1){
                    return false;
                }
            }
        }
        return true;
    }
}

public class Test {
    public static void main(String[] args) {
        new Solution().checkDistances("abaccb", new int[]{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
        new Solution().checkDistances("aa", new int[]{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
    }
}

【代码】LeeCode-模拟

由于题目中每个字母恰好出现两次，因此我们使用数组 firstIndex记录每个字母从左到右第一次出现的位置，当该字母第二次出现时，减去第一次出现的位置即可得到两个相同字母之间的字母数量。

初始化 firstIndex中的元素全为 0，为了方便计算，记录字符 s[i]出现的位置为 i+1。

按照上述检测所有的字符，如果所有的字符都满足匀整性，则返回 true，否则返回 false

package com.company;
import java.util.*;
// 2023-04-09

class Solution {
    public boolean checkDistances(String s, int[] distance) {
        int[] firstIndex = new int[26];
        for (int i = 0; i < s.length(); i++){
            int idx = s.charAt(i) - 'a';
            if (firstIndex[idx] != 0 && i - firstIndex[idx] != distance[idx]){
                return false;
            }
            // 第2次的i - 第一次的idx - 1 == 中间出现的次数
            firstIndex[idx] = i + 1;
        }
        return true;
    }
}

public class Test {
    public static void main(String[] args) {
        new Solution().checkDistances("abaccb", new int[]{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
        new Solution().checkDistances("aa", new int[]{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
    }
}

【代码】admin-枚举

思路： s字符先去重, 然后判断前后2个相同字符出现的下标是否等于distance[i]中对应的值

181 / 335 个通过的测试用例     代码不完善, 没考虑distance[i]中字符没出现的处理

package com.company;
import java.util.*;
// 2023-04-09

class Solution {
    public boolean checkDistances(String s, int[] distance) {
        List<String> list = Arrays.asList(s);
        Set<String> set = new HashSet<>(list);
        String[] strings = set.stream().toArray(String[]::new);

        for (int i = 0; i < strings.length; i++){
            int idx = strings[i].charAt(i) - 'a';
            int left = s.indexOf(strings[i]);
            // 如果找不到,则表示不存在
            if (left < 0) continue;
            int right = s.lastIndexOf(strings[i]);
            if (right - left - 1 != distance[idx]){
                return false;
            }
        }
        return true;
    }
}

public class Test {
    public static void main(String[] args) {
        new Solution().checkDistances("abaccb", new int[]{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
        new Solution().checkDistances("aa", new int[]{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
    }
}