Created
May 18, 2020 08:00
-
-
Save Gowtham-369/bfe7aa63d86e741a813bbc3761db31fe to your computer and use it in GitHub Desktop.
Day 17;LeetCode 30 Day may challenges
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
bool check_anagrams(vector<int>& a,vector<int>& b){ | |
if(a == b) | |
return true; | |
else | |
return false; | |
} | |
bool solve(string&s ,string& p){ | |
int m = p.size(); | |
int n = s.size(); | |
//inorder to be a subsring,s1.length() <= s2.length().i.e n>=m | |
if(m > n){ | |
return false; | |
} | |
int flag = 0; | |
vector<int> countS(26,0); | |
vector<int> countP(26,0); | |
for(int i=0; i<m; i++){ | |
countS[s[i]-'a']++; | |
countP[p[i]-'a']++; | |
} | |
for(int i=m; i<n; i++){ | |
if(check_anagrams(countS,countP)){ | |
flag = 1; | |
break; | |
} | |
//adding right character to make size of anagram(moving right pointer) | |
countS[s[i]-'a']++; | |
//removing previos leftmost character | |
countS[s[i-m]-'a']--; | |
} | |
if(flag) | |
return true; | |
//after adding rightmost character | |
if(check_anagrams(countS,countP)){ | |
return true; | |
} | |
return false; | |
} | |
bool checkInclusion(string s1, string s2) { | |
return solve(s2,s1); | |
} | |
}; | |
/* | |
bool compare(vector<int>& a,vector<int>& b){ | |
if(a == b) | |
return true; | |
else | |
return false; | |
} | |
bool solve(string&s ,string& p){ | |
int m = p.size(); | |
int n = s.size(); | |
if(m > n){ | |
return false; | |
} | |
int flag = 0; | |
//(a-z) = (97,122);(A-Z)=(65-90) | |
vector<int> countS(256,0);//character ascii_values array | |
vector<int> countP(256,0); | |
for(int i=0; i<m; i++){ | |
countS[s[i]]++; | |
countP[p[i]]++; | |
} | |
for(int i=m; i<n; i++){ | |
if(compare(countS,countP)){ | |
flag = 1; | |
break; | |
} | |
//adding right character to make size of anagram(moving right pointer) | |
countS[s[i]]++; | |
//removing previos leftmost character | |
countS[s[i-m]]--; | |
} | |
if(flag) | |
return true; | |
//after adding rightmost character | |
if(compare(countS,countP)){ | |
return true; | |
} | |
return false; | |
} | |
bool checkInclusion(string s1, string s2) { | |
//remember anagram is of size p.length() | |
return solve(s2,s1); | |
} | |
*/ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string. | |
Example 1: | |
Input: s1 = "ab" s2 = "eidbaooo" | |
Output: True | |
Explanation: s2 contains one permutation of s1 ("ba"). | |
Example 2: | |
Input:s1= "ab" s2 = "eidboaoo" | |
Output: False | |
Note: | |
The input strings only contain lower case letters. | |
The length of both given strings is in range [1, 10,000]. | |
HINTS: | |
Hide Hint #1 | |
Obviously, brute force will result in TLE. Think of something else. | |
Hide Hint #2 | |
How will you check whether one string is a permutation of another string? | |
Hide Hint #3 | |
One way is to sort the string and then compare. But, Is there a better way? | |
Hide Hint #4 | |
If one string is a permutation of another string then they must one common metric. What is that? | |
Hide Hint #5 | |
Both strings must have same character frequencies, if one is permutation of another. Which data structure should be used to store frequencies? | |
Hide Hint #6 | |
What about hash table? An array of size 26? |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment