LC.P2399[检查相同字母间的距离]

方法一：暴力

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;
    }
}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(1)$

方法二：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean checkDistances(String s, int[] distance) {
        int n = s.length();
        int[] d = new int[26];
        for (int i = 0; i < n; ++i) {
            int index = s.charAt(i) - 'a';
            if (d[index] > 0 && i - d[index] != distance[index]) {
                return false;
            }
            d[index] = i + 1;
        }
        return true;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(C)$，本题中$C=26$