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".METHOD 1:
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer>result = new ArrayList<Integer>();
char []pArr = p.toCharArray();
int pLength = p.length(), sLength = s.length();
Arrays.sort(pArr);
int i;
for(i=0;i<sLength;i++){
if(p.contains(s.charAt(i)+"") && (i+pLength <= sLength)){
String tmp = s.substring(i, i+pLength);
char []tmpArr = tmp.toCharArray();
Arrays.sort(tmpArr);
if(Arrays.equals(pArr, tmpArr)){
result.add(i);
}
}
}
return result;
}
}
Here, we are going to solve only using String and Arrays.
The idea behind this solution is if p string contains any character
from s string, then check for entire p string in s
string. This can be done by sorting p array and
substring array and finally check for equality.
It is another easiest way to find anagrams in a String using Java
Below are steps to be followed..,
1) Create a list to store a list of anagrams.
2) Convert p string to char array and sort it using Arrays.sort().
3) Now, iterate each character in entire s string and if any character of s
string found in p string then.,
a) Find substring exactly equal to length of p string from current
charcter.
b) Convert substring to char array and sort it.
c) After sorting, check for equality. If both are equals, then add it to
result list.
4) Repeat above step until you reach end of s string,
5) i+pLength <= sLength condition is used because while doing substring it
should go beyond s string length.
Above solution seems to be very easy, but if you check
runtime (1657 ms approx)
it is one of most time consumption solution.
METHOD 2:
class Solution {
public List<Integer>
findAnagrams(String s, String p) {
List<Integer> result= new ArrayList<>();
int[] count= new int[128];
for
(char c : p.toCharArray()) count[c]--;
for (int r = 0, l = 0; r < s.length(); r++) {
if (++count[s.charAt(r)] > 0) { //step 1
while (s.charAt(l) != s.charAt(r)) // step2
count[s.charAt(l++)]--;
count[s.charAt(l++)]--; // step 3
} else if (r - l + 1 == p.length()) { //step 4
result.add(l);
count[s.charAt(l++)]--; // step 5
}
}
return result;
}
}
This solution will be little bit confusing until you done a execution with pen
and paper. Here, we are going to create a temporary array with size of 128 and
with help of this array we are going to find substring. Please follow step
number as mentioned in code.
Initial we are adding p string to array by decrementing 1.
1) If number of characters in string s[r] is more than our needed length, then
2) In this we are going to remove until we found string s[r]
3) In this we remove s[r] so that count[s[r]] will be 0.
4) If size of our numbers is equal to p string length then add l to the result
list.
5) Repeat above al steps till end of s string.
Related Posts:
Click here for May month challenges with solution and explanation
Click here for April month challenges with solution and explanation
Click here for May month challenges with solution and explanation
Click here for April month challenges with solution and explanation
Click Follow button to receive updates from us instantly.
Please let us know about your views in comment section.
Comments
Post a Comment