Find All Anagrams in a String

2023-12-27 04:59

文章标签 string find anagrams

本文主要是介绍Find All Anagrams in a String，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址：https://leetcode.com/problems/find-all-anagrams-in-a-string/

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"Output:
[0, 6]Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"Output:
[0, 1, 2]Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

这个题目的意思就是说在字符串s中，是否存在这样的子字符串，这个子字符串是字符串p的一种排列，如果存在，这输出这样的子字符串的所有的位置。

首先假如说s中存在这样的子字符串substr，那么substr的长度肯定跟p的长度是相等的。下来就是比较substr与p的关系了，是不是互为一种排列。

确定这种关系有很多种，比如将p和substr都排个序，然后比较排个序的两个字符串是不是相等，相等则互为排列，不相等则不互为排列。

或者用p中的每一个字符与substr中的字符比较，看是否存在，如果存在，则移除，注意：这一步移除很重要，如果不移除，很可能会重复比较，比如“ab”和“aa”，继续比较，直到p中的字符遍历完。如果不存在，那么就不再往下比较了，继续进行下一轮迭代。

实现代码如下：

public class FindAllAnagramsInAString {public List<Integer> findAnagrams(String s, String p) {List<Integer> result = new ArrayList<Integer>();int pLen = p.length();for (int i = 0; i <= s.length() - pLen; i++) {String subStr = s.substring(i, i + pLen);boolean isTrue = true;for (int j = 0; j < pLen; j++) {if (subStr.indexOf(p.charAt(j)) == -1) {isTrue = false;break;} else {subStr = subStr.substring(0, subStr.indexOf(p.charAt(j))) + subStr.substring(subStr.indexOf(p.charAt(j)) + 1);continue;}}if (isTrue)result.add(i);}return result;}public static void main(String[] args) {FindAllAnagramsInAString findAllAnagramsInAString = new FindAllAnagramsInAString();System.out.println(findAllAnagramsInAString.findAnagrams("baa", "aa"));}
}