2399-检查相同字母间的距离

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

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

方法一：枚举

思路与算法

直接枚举所有相同的字符对 (s[i],s[j])，且满足 s[i]=s[j],i<j，此时两个相同字符之间的字母数量为 j - i - 1，然后检测该字符的匀整性。

假设字符 s[i] 在字符集中的顺序为 idx，此时只需要判断 j - i - 1 是否等于给定的 distance}[\textit{idx}] 即可。

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

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool checkDistances(string s, vector<int>& distance) {
        int n = s.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j] && distance[s[i] - 'a'] != j - i - 1) {
                    return false;
                }
            }
        }
        return true;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean checkDistances(String s, int[] distance) {
        int n = s.length();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j) && distance[s.charAt(i) - 'a'] != j - i - 1) {
                    return false;
                }
            }
        }
        return true;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
class Solution:
    def checkDistances(self, s: str, distance: List[int]) -> bool:
        n = len(s)
        for i in range(n):
            for j in range(i + 1, n):
                if s[i] == s[j] and distance[ord(s[i]) - ord('a')] != j - i - 1:
                    return False
        return True
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public bool CheckDistances(string s, int[] distance) {
        int n = s.Length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j] && distance[s[i] - 'a'] != j - i - 1) {
                    return false;
                }
            }
        }
        return true;
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
bool checkDistances(char * s, int* distance, int distanceSize) {
    int n = strlen(s);
    for (int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            if (s[i] == s[j] && distance[s[i] - 'a'] != j - i - 1) {
                return false;
            }
        }
    }
    return true;
}
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
func checkDistances(s string, distance []int) bool {
    n := len(s)
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if s[i] == s[j] && distance[s[i] - 'a'] != j - i - 1 {
                return false
            }
        }
    }
    return true
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
var checkDistances = function(s, distance) {
    let n = s.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (s[i] == s[j] && distance[s.charCodeAt(i) - 'a'.charCodeAt(0)] != j - i - 1) {
                return false;
            }
        }
    }
    return true;
};

复杂度分析

  • 时间复杂度：O(n^2)，其中 n 表示字符串的长度。我们枚举所有可能相等的字符对，一共最多有 n^2 个不同的字符对，因此时间复杂度为 O(n^2)。

  • 空间复杂度：O(1)。

方法二：模拟

思路与算法

由于题目中每个字母恰好出现两次，因此我们使用数组 firstIndex 记录每个字母从左到右第一次出现的位置，当该字母第二次出现时，减去第一次出现的位置即可得到两个相同字母之间的字母数量。初始化 firstIndex 中的元素全为 0，为了方便计算，记录字符 s[i] 出现的位置为 i + 1。按照上述检测所有的字符，如果所有的字符都满足匀整性，则返回 true，否则返回 false。

代码

[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool checkDistances(string s, vector<int>& distance) {
        vector<int> firstIndex(26);
        for (int i = 0; i < s.size(); i++) {
            int idx = s[i] - 'a';
            if (firstIndex[idx] && i - firstIndex[idx] != distance[idx]) {
                return false;
            }
            firstIndex[idx] = i + 1;
        }
        return true;
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
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;
            }
            firstIndex[idx] = i + 1;
        }
        return true;
    }
}
[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def checkDistances(self, s: str, distance: List[int]) -> bool:
        n = len(s)
        firstIndex = [0] * 26;
        for i in range(n):
            idx = ord(s[i]) - ord('a');
            if firstIndex[idx] and i - firstIndex[idx] != distance[idx]:
                return False
            firstIndex[idx] = i + 1
        return True
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public bool CheckDistances(string s, int[] distance) {
        int[] firstIndex = new int[26];
        for (int i = 0; i < s.Length; i++) {
            int idx = s[i] - 'a';
            if (firstIndex[idx] != 0 && i - firstIndex[idx] != distance[idx]) {
                return false;
            }
            firstIndex[idx] = i + 1;
        }
        return true;
    }
}
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
bool checkDistances(char * s, int* distance, int distanceSize) {
    int n = strlen(s);
    int firstIndex[26];
    memset(firstIndex, 0, sizeof(firstIndex));
    for (int i = 0; i < n; i++) {
        int idx = s[i] - 'a';
        if (firstIndex[idx] && i - firstIndex[idx] != distance[idx]) {
            return false;
        }
        firstIndex[idx] = i + 1;
    }
    return true;
}
[sol2-Go]
1
2
3
4
5
6
7
8
9
10
11
func checkDistances(s string, distance []int) bool {
    firstIndex := make([]int, 26)
    for i := 0; i < len(s); i++ {
        idx := s[i] - 'a'
        if firstIndex[idx] != 0 && i - firstIndex[idx] != distance[idx] {
            return false
        }
        firstIndex[idx] = i + 1
    }
    return true
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
var checkDistances = function(s, distance) {
    let firstIndex = new Array(26).fill(0);
    for (let i = 0; i < s.length; i++) {
        let idx = s.charCodeAt(i) - 'a'.charCodeAt(0);
        if (firstIndex[idx] != 0 && i - firstIndex[idx] != distance[idx]) {
            return false;
        }
        firstIndex[idx] = i + 1;
    }
    return true;
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 表示字符串的长度。只需要遍历字符串一次即可，总的时间复杂度为 O(n)。

  • 空间复杂度：O(|\Sigma|)，其中 |\Sigma| 表示字符集的大小，在本题中 |\Sigma| = 26。只需要记录每个字母第一次出现的位置，需要的空间为 O(|\Sigma|)。

 Comments
On this page
2399-检查相同字母间的距离