用Java写出:找到字符串中所有字母异位词
时间: 2023-11-28 17:20:16 浏览: 102
可以使用滑动窗口和哈希表来解决这个问题。具体步骤如下:
1. 定义一个哈希表,用于记录目标字符串中每个字符出现的次数。
2. 定义两个指针 left 和 right,分别表示滑动窗口的左右边界。
3. 初始化 left 和 right 为 0,表示滑动窗口的大小为 0。
4. 遍历目标字符串,每次将 right 指针向右移动一格,并将对应的字符出现次数加一。
5. 如果 right - left == p.length(),说明滑动窗口的大小已经达到了目标字符串 p 的长度,此时需要判断滑动窗口中的字符是否是 p 的一个字母异位词。
6. 判断方法是比较滑动窗口中的字符出现次数和 p 中每个字符出现次数是否一致,如果一致则说明找到了一个字母异位词。
7. 将 left 指针向右移动一格,同时将对应的字符出现次数减一,继续遍历目标字符串。
Java 代码实现如下:
```
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (s == null || s.length() == 0 || p == null || p.length() == 0) {
return result;
}
int[] hash = new int[26];
for (char c : p.toCharArray()) {
hash[c - 'a']++;
}
int left = 0, right = 0, count = p.length();
while (right < s.length()) {
if (hash[s.charAt(right) - 'a'] > 0) {
count--;
}
hash[s.charAt(right) - 'a']--;
right++;
if (count == 0) {
result.add(left);
}
if (right - left == p.length()) {
if (hash[s.charAt(left) - 'a'] >= 0) {
count++;
}
hash[s.charAt(left) - 'a']++;
left++;
}
}
return result;
}
```
阅读全文