Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
We check whether there's a substring of b, which has same size and same characters with a.
bool hasAnagramSubstring(const string& src, const string& target)
{
if(target.size() > src.size()) return false;
int srcLen = src.size(), targetLen = target.size();
int targetCount[128] = {0}, count[128] = {0}, i, j;
//initialize
for(i = 0; i < target.size(); ++i){
++targetCount[target[i]];
++count[src[i]];
}
//loop
i = 0;
while(true){
//check if substring is an anagram
for(j = 0; j < targetLen; ++j){
if(count[target[j]] != targetCount[target[j]]) break;
}
if(j == targetLen) return true;
//slide window
if(i + 1 + targetLen > srcLen) break;
--count[src[i]];
++count[src[i + targetLen]];
++i;
}
return false;
}
Odd that the good solution is just lying there with 0 votes, but a very bad solution gets 3 net upvotes.
upvoting this one as you are not trying to find all anagrams and then doing a string match which is an extensive process. Good one :)
Let me try to explain the sliding window.
We calculate the histogram of string a (length 3). Then we calculate the historgram of the first 3 characters of string b. If it doesn't matches we calculate the histogram of the next set of 3 chars which are at position 1,2,3 and then next 3 which are 2,3,4 etc So it behaves as if we are sliding a windows across the length of string a. Hope it helps.
These cases don't work with this solution
("abcdefg", "abcfedgsfdaf")
("a", "cdsgsdgsa")
("abc", "ccccccabbbbbbb")
You can improve this solution. This solution is O(nm), n = lenght of src, m = length of target. We can do this in O(n) time.
In your code above, to check if a substring is an anagram takes O(m).
//check if substring is an anagram
for(j = 0; j < targetLen; ++j){
if(count[target[j]] != targetCount[target[j]]) break;
}
You may do this in O(1) time. Maintain an int variable matchedCount that counts the number of matched characters in current substring(window) and target.
Store target chars in a HashSet to be able to use set.contains() which is O(1).
As you slide the window 1 step to the right, check the following:
1. Decrement matchedCount if the dropped character from the prev window is in target string (use the hashset to query) and if the count of that character after dropping it is now less than its target count.
2.Increment matchedCount if the new character in the new window is in target string (hashset) and if count of that character was less than the targetCount before it was added.
For each iteration (each window), check if matchedCount == target.length() and return true if it is.
Overall time complexity is n * O(1) = O(n)
The suggestion from j is not gone a work.
eg. text ="AAABABAA" and pattern="AAAB"
when the sub string is "BABA", the matchedCount will become 4 and this is wrong.
My solution is here:
public static boolean checkAnagram(String a, String b){
int lena=a.length();
int lenb=b.length();
if(lena>lenb)
return false;
if(lena==0||lenb==0){
return true;
}
boolean[] checkTable=new boolean[256];
boolean[] tempTable=new boolean[256];
for(int i=0;i<lena;i++){
tempTable[a.charAt(i)]=true;
}
int count=0;
checkTable=(boolean[]) tempTable.clone();
for(int i=0;i<lenb;i++){
if(checkTable[b.charAt(i)]==true){
count++;
if(count==lena)
return true;
checkTable[b.charAt(i)]=false;
}else{
checkTable=(boolean[]) tempTable.clone();
count=0;
}
}
return false;
}
// short and clear
public class Test
{
public static void main(String[] args)
{
Test t=new Test();
System.out.println(t.checkAnagram("afdgzyxksldfm","xyz"));
}
private boolean checkAnagram(String value, String pattern)
{
int [] pat =new int[128];
int j = 0;
for(int i=0;i<pattern.length();i++)
{
pat[pattern.charAt(i)]++;
}
for (int i=0;i<value.length();i++)
{
if(pat[value.charAt(i)]!=0)
{
for(j=1;j<pattern.length();j++)
{
if(pat[value.charAt(i+j)]==0)
break;
}
if(j==pattern.length())
{
return true;
}
}
}
return false;
}
}
My solution:
1- Sort characters of a
2- For each contiguous-character substring S of length == a.Length in b
2.1- Sort the characters of S
2.2- if S == a, return true
3- return false
public bool ContainsAnagram(string a, string b)
{
if (b.Length < a.Length) return false;
char[] aArray = a.ToArray<char>();
Array.Sort(aArray);
a = new string(aArray);
for (int i = 0; i <= b.Length - a.Length; i++)
{
string sub = b.Substring(i, a.Length);
char[] subArray = sub.ToArray<char>();
Array.Sort(subArray);
sub = new string(subArray);
if (string.Compare(sub, a, false) == 0) return true;
}
return false;
}
This solution could be improved this way: instead of sorting each substring (line: "Array.Sort(subArray)") as we move the sliding window through the big string, we can just delete one occurrence of the last character of the substring visited in the previous iteration from the current window's string, and insert-sort the character visited on the current iteration in the current window's string. This small part of the algorithm is only O(M) (M being the length of the anagram string), instead of O(MlogM) which is what it takes to sort it each time. I might publish the code later.
Correct me if I am wrong. Considering length of 'a' as m and 'b' as n, time complexity would be O(n*mlogm) for the naive approach and would be O(n*m) for the @danyluis' approach. This can be reduced to Time:O(n) and space:O(m) if we use hashtable
Below is a code in Java with O(n) time complexity and O(m) space complexity
public class AnagramSubstring {
public static void main(String args[]){
String a="xxyz";
String b="afyzxydgxzyxksldfm";
System.out.println(substringAnagram(a,b));
}
static boolean substringAnagram(String a, String b){
int[]table=new int[256];
Arrays.fill(table, 0);
int[]orig_table=new int[256];
Arrays.fill(orig_table, 0);
for(int i=0;i<a.length();i++){
table[a.charAt(i)]++;
orig_table[a.charAt(i)]++;
}
int count=0;
for(int i=0;i<b.length();i++){
if(table[b.charAt(i)]!=0){
table[b.charAt(i)]--;
count++;
if(count==a.length()){ //match found
return true;
}
}
else if(count > 0){ //reset
count=0;
table=orig_table.clone();
}
//else do nothing
}
return false;
}
}
For Yash's solution, I think it will return true even when all characters from a are present in b but are not contiguous. Doesnt substring mean that all characters should be contiguous?
how about this case
("aaaaaaccccb", "abc");
aaaaaaccccb // original input
aaaaaabcccc // sorted input
abc is not a sub string of original input, but is a sub string of sorted input.
Here's another solution using a sliding window.
int[] Histogram(string a, int idx, int length)
{
int buffSize = (int)('z' - 'A' + 1);
int[] hist = new int[buffSize];
for (int i = 0; i < length; i++) hist[a[i + idx] - 'A']++;
return hist;
}
bool SameHist(int[] h1, int[] h2)
{
for (int i = 0; i < h1.Length; i++)
if (h1[i] != h2[i]) return false;
return true;
}
public bool ContainsAnagramSlidingWindow(string a, string str)
{
if (string.IsNullOrEmpty(a)) return true;
if (a.Length > str.Length) return false;
int[] histA = Histogram(a, 0, a.Length); // a's total histogram
int[] histStr = Histogram(str, 0, a.Length); // str's partial histogram
int i = 0;
while (true)
{
// Compare str's partial histogram to a's histogram
if (SameHist(histA, histStr)) return true;
if (i == str.Length - a.Length) break;
// Move window one step ahead
histStr[str[i] - 'A']--;
histStr[str[i + a.Length] - 'A']++;
i++;
}
return false;
}
I like the histogram approach. Did you consider using a HashMap so you could compare histograms faster?
what about this?
Get hash of substring we are searching for (in this case "xyz") and search for that hash using Rabin-Karp or any other rolling hash algorithm. So in this case we would be searching for the hash of "xyz" (which would be the same for any anagram of "xyz") in our string.
I'd give you more votes if I could to get your answer to top. There are some pretty unreasonable answers at the top right now.
My algorithm
String a;
String b;
get a.length
start traversing b and use substring(i,n)
chk for anagram return true if found else
increment i till i+n<b.length.
code:
import java.util.*;
public class Anachk{
public boolean isAnagram(String s,String s1){//a and b in this function will have same length
char w1[]=s.toCharArray();
char w2[]=s1.toCharArray();
if(s.length()!=s1.length())
return false;
boolean ch=false;
HashMap<Character,Integer> chk=new HashMap<Character,Integer>();
for(int i=0;i<w1.length;i++){
char c=w1[i];
if(chk.containsKey(c))
chk.put(c, chk.get(c)+1);
else
chk.put(c, 1);
}
for(int i=0;i<w2.length;i++)
{
char c=w2[i];
if(chk.containsKey(c))
chk.put(c, chk.get(c)-1);
}
for(char c:chk.keySet()){
if(chk.get(c)==0)
ch=true;
else{
ch=false;
break;
}
}
return ch;
}
public void func(String a,String b){
if(0==a.length()||0==b.length()){
System.out.println("Null strings passed");
return;
}
if(a.length()>b.length()){
System.out.println("Error check length");
return;
}
int n=a.length();
int max=b.length();
int i;
boolean flag=false;
String tmp;
for(i=0;i<max;i++){
tmp="";
if(n>max)
break;
tmp=b.substring(i,n);
System.out.print(tmp+"\n");
flag=isAnagram(a,tmp);
n++;
if(flag==true)
break;
}
if(flag)
System.out.println("\nFound at(starting at): "+i+" ends at: "+(n-2));
else
System.out.println("Not found");
}
public static void main(String args[]){
Anachk z=new Anachk();
String a="xyz".toLowerCase();
String b="afdgZyxksldfm".toLowerCase();
z.func(a, b);
}
}
Here is a Java solution with test cases folks.
public class AnagramSubstring {
public static boolean hasAnagramSubstring(String small, String big) {
if (small == null || big == null) return false;
int aLen = small.length(), bLen = big.length();
if (bLen < aLen) return false;
byte[] a = new byte[128];
byte[] b = new byte[128];
// ASCII code as the index of arrays
for (int i = 0; i < aLen; i++) a[(int)small.charAt(i)]++;
for (int i = 0; i < bLen; i++) b[(int)big.charAt(i)]++;
int j = 0;
while (j < bLen) {
// Skip the big-str chars that are not in small-str
for (; j < bLen && a[(int)big.charAt(j)] == 0; j++);
// See if we can contiguously match 'aLen' chars in big-str
int k = 0, z = j;
while (j < bLen) {
int c = (int)big.charAt(j);
if (a[c] == 0) break;
a[c]--;
k++; if (k == aLen) return true;
j++;
}
j = z + 1;
// Since we decr the 'a' array elems above, reinit it for next try
for (int i = 0; i < aLen; i++) a[(int)small.charAt(i)]++;
}
return false;
}
public static void main(String[] args) {
String[] testData = new String[] {
// small-str big-str expected
null, null, "false",
null, "", "false",
null, "a", "false",
"a", null, "false",
"a", "", "false",
"a", "a", "true",
"ab", "a", "false",
"ab", "b", "false",
"ab", "ab", "true",
"ab", "ba", "true",
"ab", "aab", "true",
"ab", "abb", "true",
"ab", "zabf", "true",
"ab", "zbaf", "true",
"aab", "zadaabf", "true",
"aab", "zadabaf", "true",
"aab", "zadabaaf", "true",
"aabc", "fbebadabacf", "true",
"aabc", "fbebadbadf", "false",
"aabc", "fooabca", "true"
};
for (int j = 0; j < testData.length; j += 3) {
boolean actual = hasAnagramSubstring(testData[j], testData[j+1]);
boolean expected = Boolean.parseBoolean(testData[j+2]);
System.out.printf("|-> %s!. hasAnagramSubstr('%s', '%s') must be '%s'. "
+ "Got '%s'\n",
(actual == expected ? "Pass" : "Fail"),
testData[j], testData[j+1], expected, actual );
}
}
}
And the output:
|-> Pass!. hasAnagramSubstr('null', 'null') must be 'false'. Got 'false'
|-> Pass!. hasAnagramSubstr('null', '') must be 'false'. Got 'false'
|-> Pass!. hasAnagramSubstr('null', 'a') must be 'false'. Got 'false'
|-> Pass!. hasAnagramSubstr('a', 'null') must be 'false'. Got 'false'
|-> Pass!. hasAnagramSubstr('a', '') must be 'false'. Got 'false'
|-> Pass!. hasAnagramSubstr('a', 'a') must be 'true'. Got 'true'
|-> Pass!. hasAnagramSubstr('ab', 'a') must be 'false'. Got 'false'
|-> Pass!. hasAnagramSubstr('ab', 'b') must be 'false'. Got 'false'
|-> Pass!. hasAnagramSubstr('ab', 'ab') must be 'true'. Got 'true'
|-> Pass!. hasAnagramSubstr('ab', 'ba') must be 'true'. Got 'true'
|-> Pass!. hasAnagramSubstr('ab', 'aab') must be 'true'. Got 'true'
|-> Pass!. hasAnagramSubstr('ab', 'abb') must be 'true'. Got 'true'
|-> Pass!. hasAnagramSubstr('ab', 'zabf') must be 'true'. Got 'true'
|-> Pass!. hasAnagramSubstr('ab', 'zbaf') must be 'true'. Got 'true'
|-> Pass!. hasAnagramSubstr('aab', 'zadaabf') must be 'true'. Got 'true'
|-> Pass!. hasAnagramSubstr('aab', 'zadabaf') must be 'true'. Got 'true'
|-> Pass!. hasAnagramSubstr('aab', 'zadabaaf') must be 'true'. Got 'true'
|-> Pass!. hasAnagramSubstr('aabc', 'fbebadabacf') must be 'true'. Got 'true'
|-> Pass!. hasAnagramSubstr('aabc', 'fbebadbadf') must be 'false'. Got 'false'
|-> Pass!. hasAnagramSubstr('aabc', 'fooabca') must be 'true'. Got 'true'
/*
* Find if any anagram of a, is present as a substring in b.
* Returns offset of string b, where anagram can be found.
* Otherwise: Returns NULL
*/
char * find_anagram(char *a, char *b)
{
if (!a || !b) return NULL;
int i, j;
int offset = 0;
int alen = strlen(a);
int blen = strlen(b);
char hash[256] = {0};
for (i = 0; i < alen; i++) {
hash[a[i]]++;
}
for (i = 0; i < blen; i++) {
/* If char available, decrement count,
* return if this was the last character to match
*/
if (hash[b[i]] > 0) {
hash[b[i]]--;
if (i-offset+1 == alen) {
return b+offset;
}
} else { /* If character not present OR if character exhausted,
* then remove the prefix starting from offset, until we
* find first character with the same value as current character
* i.e. b[i], At that point, move answer(offset) further.
* Example: a = "pqrp"; b = "rqpqpptpqprz";
*/
for (j=offset; b[j]!=b[i]; j++) {
hash[b[j]]++;
}
offset = j+1;
}
}
return NULL;
}
package com.self.learning.interview.google;
import java.util.regex.Pattern;
public class AnagramTest {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
// Anagram = forming a new word by rearranging the characters of a word
// like tail from ital
String s1 = "xyz";
String s2 = "yzxafdgksldfm";
System.out.println(checkAnagram(s1,s2));
}
private static boolean checkAnagram(String s1, String s2){
boolean found = false;
StringBuilder pattern = new StringBuilder();
int len = s1.length();
for(int i=0;i<len;i++){
pattern.append('[');
pattern.append(s1);
pattern.append(']');
}
System.out.println("regex : "+pattern);
Pattern p = Pattern.compile(pattern.toString());
found = p.matcher(s2).find();
return found;
}
}
Initialize an array of 26 slots each with the number of times every character appears on string a and then create a copy for such array.
For each character in string b, check if the count on the previously copied array is zero, if so reset the copied array to its original status. Otherwise, decrement the counter and check if all items in the array are now zero, if so, you've found a valid sub-string.
After the for-loop has ended, is safely to assume that no sub-string exists in b.
Time complexity: O(|b|)
Space complexity: O(1)
inline void reset_stats(
const char origin_stats [],
const int origin_count,
char target_stats [],
int& target_count)
{
for (int index = 0; index < 26; index++)
target_stats[index] = origin_stats[index];
target_count = origin_count;
}
bool is_substr(const string& pattern, const string& search_txt)
{
if (pattern.length() == 0)
return true;
if (pattern.length() > search_txt.length())
return false;
int origin_count = pattern.length();
char origin_stats [26] = { 0 };
for (int index = 0; index < pattern.length(); index++)
origin_stats[pattern[index] - 'a']++;
int current_count;
char current_stats [26] = { 0 };
reset_stats(
origin_stats, origin_count, current_stats, current_count);
for (int index = 0; index < search_txt.length(); index++)
{
if (current_stats[search_txt[index] - 'a'] == 0)
reset_stats(
origin_stats, origin_count, current_stats, current_count);
else
{
current_stats[search_txt[index] - 'a']--;
current_count--;
if (current_count == 0)
return true;
}
}
return false;
}
Almost correct. However there is a bug in the code. The worst case time complexity is O(NM) where N is length of search string and M is length of pattern string.
Pattern: aabb
Search String : xxbabba
When you are on first 'b' of search string, you start comparing aabb to babba and at last 'b' of search string, you will realize that pattern doesn't match (aabb is not anagram of babb), so instead of simply skipping, we need to compare aabb to abba and return true.
To optimize, this requires to apply KMP algorithm so we can reduce time complexity from O(NM) to O(N)
your code can be fixed as below
for (int index = 0; index < search_txt.length(); index++)
{
if (current_stats[search_txt[index] - 'a'] == 0)
reset_stats(
origin_stats, origin_count, current_stats, current_count);
else
{
if(current_stats[search_txt[index] - 'a'] > 0)
{ // consider this as a match
current_stats[search_txt[index] - 'a']--;
current_count--;
}
else
{
int cur_index = original_count-current_count;
// we matched cur_index characters,
// remove first character from consideration
current_stats[search_txt[index-cur_index] - 'a']++;
}
if (current_count == 0)
return true;
}
}
@mithya
I am not familiar with KMP, but I like what your attempting to do. Resetting the first value that was decremented in the "current_stats" array once you've realized it does not fit in the pattern. Your proposed solution however seems flawed. It appears that the else statement you've added is unreachable. The above code will catch if a value is 0 in the array (and reset), or greater than zero (and decrement it by one). Since no values start at < 0, you will never get to your new code. Also, the current_count variable becomes disjointed with the current_stats array when the increment takes place. This may be by design but if so it's very confusing.
Yes, I realized that. The if part will check for -1 instead. Idea is in array 26, default value should be -1, or a large value e.g. strlen(search_string)+1 because
// Check if the character at all belonged into pattern string
if (current_stats[search_txt[index] - 'a'] == -1 or large value)
{
// Reset and continue
}
else
{
}
@Mithya Thanks for your observation!! You're right, I totally missed that case. Please take a look at this other solution I'm proposing that doesn't require KMP and still achieves O(|b|) time complexity with O(1) space:
The idea is to keep an index of the start of the sub-string initially pointing to zero and while reading the search string from left to right check:
a) If the counter in origin_stats for the current character is zero that means that current element is not part of a valid sub-string and it's safe to reset the current stats. Also, start index of sub-string can be changed to index + 1.
b) Else if the counter in current_stats for the current character has become zero, then we need to either regain a character with the same value along the current sub-string and update the start index so that the solution doesn't include it or forfeit the current sub-string if we weren't able to find one.
c) Else just decrement the counter in current_stats and see if we have already found all required characters (this is unchanged from my previous solution).
Cool thing about this is that we're now able to determine the start of the valid sub-string whenever one exists. Here's the code:
inline void reset_stats(
const char origin_stats [],
const int origin_count,
char target_stats [],
int& target_count)
{
for (int index = 0; index < 26; index++)
target_stats[index] = origin_stats[index];
target_count = origin_count;
}
bool is_substr(const string& pattern, const string& search_txt)
{
if (pattern.length() == 0)
return true;
if (pattern.length() > search_txt.length())
return false;
int origin_count = pattern.length();
char origin_stats [26] = { 0 };
for (int index = 0; index < pattern.length(); index++)
origin_stats[pattern[index] - 'a']++;
int current_count;
char current_stats [26] = { 0 };
reset_stats(
origin_stats, origin_count, current_stats, current_count);
int substr_start = 0;
for (int index = 0; index < search_txt.length(); index++)
{
if (origin_stats[search_txt[index] - 'a'] == 0)
{
reset_stats(
origin_stats, origin_count, current_stats, current_count);
substr_start = index + 1;
}
else if (current_stats[search_txt[index] - 'a'] == 0)
{
while (search_txt[substr_start] != search_txt[index])
{
current_stats[search_txt[substr_start] - 'a']++;
substr_start++;
current_count++;
}
if (substr_start != index)
substr_start++;
}
else
{
current_stats[search_txt[index] - 'a']--;
current_count--;
if (current_count == 0)
return true;
}
}
return false;
}
Nice meh. I would however suggest a quicker reset method. A memcpy would work nice here considering your array is constant size.
Also a quick question for Mithya...
Meh's fix would still run in linear time but as it is now O(2b) it is slightly less optimal. Your original attempt at fixing this did not introduce a second loop. You've modified your if statements to check for negative values to determine if the character exists in the patter, but Meh's solution now has a similar check. I'm wondering if you could post a corrected full implementation to show how this could be done without the use of a second loop (if you still believe it is possible). Thanks
*EDITED*
I don't know much about time complexities and whatnot, but this definitely works!
public class AnagramChecker {
// Find whether n contains a subset of an anagram of m:
public Boolean hasAnagram (String n, String m) {
char A[] = n.toCharArray();
char B[] = m.toCharArray();
boolean index[] = new boolean [A.length];
int counter = 0;
// Search B for an anagram of A, return true if found
for (int b = 0; b < ( B.length - A.length + 1); b++) { // Loop through B
for (int d = 0; d < index.length; d++) // Reset the record
index[d] = false;
for (int a = 0; a < A.length; a ++ ) { // Loop through A
for (int c = b; c < ( b + A.length ); c++) { // Loop through the possible Bs
if (!index[a]) { // If the A char has not been matched
if ( A[a] == B[c] ) { // If there is a match,
index[a] = true; // record the match
if ( a == (A.length - 1)) { // If it is the last A char to match
for (int d = 0; d < index.length; d++) { // Check to see if all As matched
if (index[d])
counter++;
}
if ( counter == index.length )
return true; // If all matched, return true
counter=0; // Reset the counter if no match found
}
}
}
}
}
}
// If no anagram found, return false
return false;
}
// Test the function:
public static void main (String[] args) {
AnagramChecker AC = new AnagramChecker();
String first = "supercali";
String second = "fragilistic";
String third = "expialidocious";
String anagram = "dial";
if(AC.hasAnagram(anagram, first))
System.out.println(first + " contains an anagram of dial");
else System.out.println(first + " does not contain an anagram of dial");
if(AC.hasAnagram(anagram, second))
System.out.println(second + " contains an anagram of dial");
else System.out.println(second + " does not contain an anagram of dial");
if(AC.hasAnagram(anagram, third))
System.out.println(third + " contains an anagram of dial");
else System.out.println(third + " does not contain an anagram of dial");
}
}
I just add a main method to run it and put it in my IDE and it works perfectly. (There were a few bugs, but I haven't hand written code in forever!)
public class AnagramChecker {
// Find whether String b contains a subset of an anagram of String a:
public Boolean hasAnagram (String n, String m) {
char A[] = n.toCharArray();
char B[] = m.toCharArray();
// Search B for A backwards, return true if found
for (int b = 0; b < ( B.length - A.length + 1 ); b++) { // Loop through B
for (int a = ( A.length - 1 ); a >= 0; a -- ) { // Loop through A
if( B[b] == A[a]) { // Check
b++; // Check the next cell
if( a< 1 )
return true; // If all checks worked, return true
}
else { // If a check failed, reset values
b = b - ((A.length - 1) - a);
a = 0;
}
}
}
// If no anagram found, return false
return false;
}
// Test the function:
public static void main (String[] args) {
AnagramChecker AC = new AnagramChecker();
String first = "supercali";
String second = "fragilistic";
String third = "expialidocious";
String anagram = "ila";
System.out.println("ali is an anagram of ila");
if(AC.hasAnagram(anagram, first))
System.out.println(first + " contains the anagram");
else System.out.println(first + " does not contain the anagram");
if(AC.hasAnagram(anagram, second))
System.out.println(second + " contains the anagram");
else System.out.println(second + " does not contain the anagram");
if(AC.hasAnagram(anagram, third))
System.out.println(third + " contains the anagram");
else System.out.println(third + " does not contain the anagram");
}
}
^^^ Anagram doesn't mean "reverse of the word" :)
You maybe need more test cases. Try searching for "abc" inside "zzzzbaczzzz" (should return true)
import java.io.*;
public class Qs5389078581215232 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
String a = br.readLine();
String b = br.readLine();
//Assuming only alphabetic string with lower alphabets
int[] count = new int[26];
int lengthB = b.length();
for (int i = 0; i < lengthB; ++i) {
char ch = b.charAt(i);
count[ch-'a']++;
}
int lengthA = a.length();
boolean result = true;
for (int i = 0; i < lengthA; ++i) {
char ch = a.charAt(i);
count[ch-'a']--;
if (count[ch-'a'] < 0) {
result = false;
break;
}
}
out.println(result);
out.flush();
out.close();
System.exit(0);
}
}
Things to note :
1. Difference b/w substring and subsequence
2. Characters can be repeated
<b> The simple approach </b>:
public static boolean hasAnagramSubstring(String a, String b) {
char[] str = a.toCharArray();
int seq = -1;
int count = 0;
String subString = "";
boolean matching = false;
// Traverse through all char in b
for (int i = 0; i < b.length(); i++) {
if (!matching) {
seq = i;
}
boolean found = false;
// For each char in b, search in a
for (int j = 0; j < str.length; j++) {
if (b.charAt(i) == str[j] && str[j] != '*') {
str[j] = '*'; // If matched, marked it as matched
found = matching = true;
subString += b.charAt(i);
if (++count == a.length()) {
System.out.println(subString);
return true;
}
break;
}
}
// Reset
if (!found && matching) {
str = a.toCharArray();
i = seq;
count = 0;
matching = false;
subString = "";
}
}
return false;
}
time (n), space o(1)
#include <string>
bool hasPattern(const string &input, const string &pattern) {
if (input.empty() || pattern.empty() || pattern.size() > input.size()) {
// error cases
return false;
}
// Uses counting on the alphabet to track anagram.
char pattern_count[26] = {0};
for (auto &c : pattern) {
++pattern_count[c - 'a'];
}
// Uses slide window of pattern size to compare whether it could be an anagram
char input_count[26] = {0};
// When extra_count equals to zero after initialization, it means it's an
// anagram.
int extra_count = 0;
for (int i = 0; i < pattern.size(); ++i) {
int index = input[i] - 'a';
++input_count[index];
if (input_count[index] > pattern_count[index]) {
++extra_count;
}
}
int i = 0;
// Moves the slide window.
while (extra_count > 0 && i < input.size() - pattern.size()) {
int index = input[i] - 'a';
if (input_count[index] > pattern_count[index]) {
--extra_count;
}
--input_count[index];
index = input[i + pattern.size()] - 'a';
++input_count[index];
if (input_count[index] > pattern_count[index]) {
++extra_count;
}
++i;
}
return extra_count == 0;
}
Why didn't somebody write the approach instead lines of code?
Iterate through text.size()-pattern.size()+1 substrings maintaining amount of each character in sliding window pattern.size() size and amount of matched characters. Whenever matched characters equals alphabet size we have found required substring.
How about this?
Sort the two strings and then find whether the 2nd contains the first as substring.
package com.techsavvykavi;
import java.util.Arrays;
public class Anagram {
/**
* @param args
*/
public static void main(String[] args) {
String a = "xyz";
String b = "afdgzyxksldfm";
boolean match = false;
char[] pattern = a.toCharArray();
char[] stringToMatch = b.toCharArray();
Arrays.sort(pattern);
Arrays.sort(stringToMatch);
StringBuilder sortedStringToMatch = new StringBuilder();
sortedStringToMatch.append(stringToMatch);
if ( sortedStringToMatch.indexOf(new String (pattern) ) == -1 )
match = false;
else
match = true;
System.out.println( match );
}
}
/*using a array of size 26 to represent characters we can easily solve it by traversing base array and checking it against anagram array /*
bool isAnagramOfAIsSubStrOfB(char *str, char *anag, int anag_size)
{
int arr[26]= {0};
int i=0, k=0, l = anag_size - 1;
while(anag[i])
arr[anag[i++]-97] = 1;
printf("\nBase String: %s", str);
printf("\nAnag String: %s", anag);
i=0;
while ( str[i] )
{
if (arr[str[i] -97] )
{
while(arr[str[i] -97])
{
arr[str[i] -97] = 0;
i++;
}
k=0;
l= anag_size - 1;
while (arr[anag[k] -97] == 0 && l--)
{
arr[anag[k]-97] = 1;
k++;
}
if( k == anag_size - 1)
return true;
//reset all relevant bits to 1
k=0;
while(anag[k])
arr[anag[k++]-97] = 1;
i--;
}
i++;
}
return false;
}
bool compare(int* countA, int* countB, int num){
for(int i = 0; i < num; ++i){
if(countA[i] != countB[i])
return false;
}
return true;
}
bool containsAnagram(string a, string b){
if(b.length() < a.length()) return false;
int countA[26];
int countB[26];
for(int i = 0; i < a.length(); ++i){
++countA[a[i] - 'a'];
}
for(int i = 0; i < a.length(); ++i){
++countB[b[i] - 'a'];
}
if(compare(countA, countB, 26))
return true;
for(int i = a.length(); i < b.length(); ++i){
--countB[b[i - a.length()] - 'a'];
++countB[b[i] - 'a'];
if(compare(countA, countB, 26))
return true;
}
return false;
}
int main(){
cout<<(containsAnagram("xyz", "ddzyxmk")?"true":"false")<<endl;
return 0;
}
bool findAnagram (char* a, char* b)
{
int cnts[256] = {0};
char c;
int alen = 0;
while ( a != NULL && *a) {
c = *a;
cnts[c]++;
alen++;
a++;
}
int total_cnt = 0;
while (b != NULL) {
c = *b;
if (--cnts[c] < 0) {
int dt = 0;
do {
cnts[*(b - dt)]++;
dt++;
}
while (dt <= total_cnt);
total_cnt = 0;
}
else
{
if (++total_cnt == alen) {
return true;
}
}
b++;
}
return false;
}
It can be done in O(m+n), where n is length of a and m is length of b
Suppose a = string whose anagrams are to be found
and b = string to be searched
Algo:
1. search for first occurrence of first character of a in b. If not found return false.
2. Suppose that location is i.
3. Now anagram can be present from i-n-1 to i+n-1 position.
4. Take next character of a and search in range found in step 3.
5. If found repeat step 4 with next character of a until length of a Else repeat step 1 starting at i+n position.
6. If all characters found return true;
bool HasAnagramSubstring(string data, string sample)
{
int lengD = data.Length;
int lengS = sample.Length;
HashSet<char> map = new HashSet<char>();
foreach (char c in sample)
{
map.add(c);
}
char[] arraySample = sample.ToCharArray();
Array.Sort(arraySample);
string sortedSample = new string(arraySample);
for (int i = 0; i < lengD - lengS; ++i)
{
bool found = true;
// find whether substring starting from i to i + lengS contains all chars
for (int j = i; j < i + lengS; ++j)
{
if (!map.find(data[j])
{
found = false;
i = j;
break;
}
}
if (found)
{
// sort the chars in the string
string temp = data.Substring(i, lengS);
char[] tempArray = temp.ToCharArray();
Array.Sort(tempArray);
// compare the string with sorted sample string
if (sample.EqualsTo(new string(tempArray)))
{
return true;
}
}
}
}
find longest common subsequence of two strings,if LCS and second string is same will return true,else return false.
// C#
// O(n + m + m/n = 2m)
public static bool IsAnagram(string a, string b)
{
if (string.IsNullOrEmpty(a) || string.IsNullOrEmpty(b))
return false;
if (a.Length > b.Length)
return false;
var dicA = new Dictionary<char, int>();
// O(n)
foreach (var ch in a)
{
if (dicA.ContainsKey(ch))
dicA[ch]++;
else
dicA.Add(ch, 1);
}
var i = 0;
while (i <= b.Length - a.Length)
{
var j = i;
var dicB = new Dictionary<char, int>();
// O(m)
while (j < i + a.Length)
{
if (dicB.ContainsKey(b[j]))
{
dicB[b[j]]++;
}
else
{
if (dicA.ContainsKey(b[j]))
dicB.Add(b[j], 1);
else
break;
}
j++;
}
if (j == i + a.Length)
{
if (dicA.Count == dicB.Count)
{
// O(n), can get into O(m/n) times
if (dicA.All(kvp => kvp.Value == dicB[kvp.Key]))
return true;
}
i = j;
}
else
{
i++;
}
}
return false;
}
Java Implementation of this problem. Time complexit o(m*n)
public static boolean isAnagramExists(String src, String target)
{
if (src == null || "".equals(src.trim()) || target == null)
{
return false;
}
Map<String, Integer> targetCount = new HashMap<String, Integer>();
Map<String, Integer> srcCount = new HashMap<String, Integer>();
int targetLen = target.length();
int srcLen = src.length();
for (int i = 0; i < target.length(); i++)
{
increaseCharCount(target, targetCount, i);
increaseCharCount(src, srcCount, i);
}
int start = 0;
while (start < srcLen)
{
int j = 0;
for (j = 0; j < targetLen; ++j)
{
String targetLetter = String.valueOf(target.charAt(j));
if (targetCount.get(targetLetter) != srcCount.get(targetLetter))
{
break;
}
}
if (j == targetLen)
{
return true;
}
if (start + 1 + targetLen > srcLen)
break;
decreaseCharCount(src, srcCount, start);
increaseCharCount(src, srcCount, start + targetLen);
start++;
}
return false;
}
private static void decreaseCharCount(String string, Map<String, Integer> map, int i)
{
String targetLetter = String.valueOf(string.charAt(i));
if (map.get(targetLetter) == null)
{
map.put(targetLetter, 0);
}
else
{
int count = map.get(targetLetter);
map.put(targetLetter, --count);
}
}
private static void increaseCharCount(String string, Map<String, Integer> map, int i)
{
String targetLetter = String.valueOf(string.charAt(i));
if (map.get(targetLetter) == null)
{
map.put(targetLetter, 1);
}
else
{
int count = map.get(targetLetter);
map.put(targetLetter, ++count);
}
}
Maybe this is not the optimal solution.. but works....
public static boolean anagram(String s1, String s2) {
char a2[] = s2.toCharArray();
Arrays.sort(a2);
String b2 = String.valueOf(a2);
return (s1.trim().equals( b2.trim() ));
}
public static boolean search(String str, String stream) {
int windowLen = str.length();
int streamLen = stream.length();
char[] a1 = str.toCharArray();
Arrays.sort(a1);
String aSorted = String.valueOf(a1);
for( int i = 0; i < streamLen - windowLen; i++ ) {
String window = stream.substring(i, i + (windowLen));
if(anagram(aSorted, window) ) {
return true;
}
}
return false;
}
An On solution as maximum time any character in the larger string is scanned is 2.
import java.io.*;
public class Qs5389078581215232 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
String a = br.readLine();
String b = br.readLine();
//Assuming only alphabetic string with lower alphabets
int[] count = new int[26];
int lengthA = a.length();
for (int i = 0; i < lengthA; ++i) {
char ch = a.charAt(i);
count[ch-'a']++;
}
fill(count, -1);
int lengthB = b.length();
int[] temp = copy(count);
int start = -1;
int matchCount = 0;
boolean found = false;
for (int i = 0; i < lengthB; ++i) {
char ch = b.charAt(i);
if (temp[ch-'a'] > 0) {
start = matchCount == 0 ? i : start;
matchCount++;
temp[ch-'a']--;
if (matchCount == lengthA) {
found = true;
break;
}
}
else if (temp[ch-'a'] == 0) {
char tempCh = b.charAt(start);
while(tempCh != ch) {
temp[tempCh-'a']++;
matchCount--;
start++;
tempCh = b.charAt(start);
}
start++;
}
else if(temp[ch-'a'] == -1) {
if (matchCount > 0) {
temp = copy(count);
matchCount = 0;
start = -1;
}
}
}
out.println(found);
out.flush();
out.close();
System.exit(0);
}
private static int[] copy(int[] A) {
int lengthA = A.length;
int[] B = new int[lengthA];
for (int i = 0; i < lengthA; ++i) {
B[i] = A[i];
}
return B;
}
private static void fill(int[] A, int num) {
int lengthA = A.length;
for (int i = 0; i < lengthA; ++i)
A[i] = A[i] > 0 ? A[i] : num;
}
}
simple order n solution would be:
1) covert string a into int value. eg if a="ab" then its value is 97+98;
2) now in the string b just iterate till length-2 converting all substrings of length 2 into integer values and compare the results.
Similar approach to Rabin-Karp string search algorithm.
// prime number based hash.
#define PRIME 103
uint64_t hash(const char *s, int len)
{
uint64_t h = 0;
for (int i = 0; i < len; ++i) {
h = h*PRIME + s[i];
}
return h;
}
int findAnagram(const char *A, const char *B, char *T)
{
int A_len = strlen(A);
int B_len = strlen(B);
if (A_len > B_len) {
return B_len;
}
// PRIME^(A_len-1)
uint64_t P = 1;
for (int i = 1; i < A_len; ++i) Hk *= PRIME;
// get hash value of input string.
uint64_t H = hash(A, A_len);
uint64_t h = hash(B, A_len);
for (int i = 0; i < (B_len - A_len); ++i) {
if (H == h) {
strncpy(T, B+i, A_len);
std::sort(T, T+A_len);
if (strncmp(A, T, A_len) == 0) {
return i;
}
}
h = h - B[i] * P + B[i+A_len];
}
return B_len;
}
Assume that A is already sorted. When a substring of B shows the same hash value with A, the substring is copied to T and compared one-by-one after being sorted. The time complexity will be O(n + c*m*logm) where n is length of B, m is length of A, and c is the number of false positive cases.
public static bool IsAnyAnagramASubstring(string a, string b)
{
var aSorted = Sort(a);
return SubstringsOfLength(b, a.Length).Any(substring => AreAnagrams(aSorted, substring));
}
// Requires a to be sorted.
private static bool AreAnagrams(string a, string b)
{
return a.Equals(Sort(b), StringComparison.Ordinal);
}
// Returns all substrings of input of the specified length.
private static IEnumerable<string> SubstringsOfLength(string input, int length)
{
for (var i = 0; i < input.Length - length; i++)
{
yield return input.Substring(i, length);
}
}
private static string Sort(string input)
{
var chars = input.ToCharArray();
Array.Sort(chars);
return new string(chars);
}
Iterate the string b, if find one char which is contained by a, compare the following a.length() substring of b with a, to see if this substring is anagram of a.
public static boolean isAnagram(String a, String b){
char[] aChars = a.toCharArray();
char[] bChars = b.toCharArray();
Arrays.sort(aChars);
Arrays.sort(bChars);
return String.copyValueOf(aChars).equalsIgnoreCase(String.copyValueOf(bChars));
}
public static void main(String[] args){
String a ="xyd";
String b= "afdgzyxksldfm";
boolean flag = false;
for(int i = 0; i<b.length(); i++){
String s = b.substring(i, i+1);
if(a.contains(s)){
s= b.substring(i, i+a.length());
if(isAnagram(a, s)){
flag = true;
break;
}
}
}
System.out.println("If string a "+a+" is contained by b "+b+" "+flag);
}
My algorithm
String a;
String b;
get a.length
start traversing b and use substring(i,n)
chk for anagram return true if found else
increment i till i+n<b.length.
code:
import java.util.*;
public class Anachk{
public boolean isAnagram(String s,String s1){//a and b in this function will have same length
char w1[]=s.toCharArray();
char w2[]=s1.toCharArray();
if(s.length()!=s1.length())
return false;
boolean ch=false;
HashMap<Character,Integer> chk=new HashMap<Character,Integer>();
for(int i=0;i<w1.length;i++){
char c=w1[i];
if(chk.containsKey(c))
chk.put(c, chk.get(c)+1);
else
chk.put(c, 1);
}
for(int i=0;i<w2.length;i++)
{
char c=w2[i];
if(chk.containsKey(c))
chk.put(c, chk.get(c)-1);
}
for(char c:chk.keySet()){
if(chk.get(c)==0)
ch=true;
else{
ch=false;
break;
}
}
return ch;
}
public void func(String a,String b){
if(0==a.length()||0==b.length()){
System.out.println("Null strings passed");
return;
}
if(a.length()>b.length()){
System.out.println("Error check length");
return;
}
int n=a.length();
int max=b.length();
int i;
boolean flag=false;
String tmp;
for(i=0;i<max;i++){
tmp="";
if(n>max)
break;
tmp=b.substring(i,n);
System.out.print(tmp+"\n");
flag=isAnagram(a,tmp);
n++;
if(flag==true)
break;
}
if(flag)
System.out.println("\nFound at(starting at): "+i+" ends at: "+(n-2));
else
System.out.println("Not found");
}
public static void main(String args[]){
Anachk z=new Anachk();
String a="xyz".toLowerCase();
String b="afdgZyxksldfm".toLowerCase();
z.func(a, b);
}
}
My algorithm
String a;
String b;
get a.length
start traversing b and use substring(i,n)
chk for anagram return true if found else
increment i till i+n<b.length.
code:
import java.util.*;
public class Anachk{
public boolean isAnagram(String s,String s1){//a and b in this function will have same length
char w1[]=s.toCharArray();
char w2[]=s1.toCharArray();
if(s.length()!=s1.length())
return false;
boolean ch=false;
HashMap<Character,Integer> chk=new HashMap<Character,Integer>();
for(int i=0;i<w1.length;i++){
char c=w1[i];
if(chk.containsKey(c))
chk.put(c, chk.get(c)+1);
else
chk.put(c, 1);
}
for(int i=0;i<w2.length;i++)
{
char c=w2[i];
if(chk.containsKey(c))
chk.put(c, chk.get(c)-1);
}
for(char c:chk.keySet()){
if(chk.get(c)==0)
ch=true;
else{
ch=false;
break;
}
}
return ch;
}
public void func(String a,String b){
if(0==a.length()||0==b.length()){
System.out.println("Null strings passed");
return;
}
if(a.length()>b.length()){
System.out.println("Error check length");
return;
}
int n=a.length();
int max=b.length();
int i;
boolean flag=false;
String tmp;
for(i=0;i<max;i++){
tmp="";
if(n>max)
break;
tmp=b.substring(i,n);
System.out.print(tmp+"\n");
flag=isAnagram(a,tmp);
n++;
if(flag==true)
break;
}
if(flag)
System.out.println("\nFound at(starting at): "+i+" ends at: "+(n-2));
else
System.out.println("Not found");
}
public static void main(String args[]){
Anachk z=new Anachk();
String a="xyz".toLowerCase();
String b="afdgZyxksldfm".toLowerCase();
z.func(a, b);
}
}
My algorithm
String a;
String b;
get a.length
start traversing b and use substring(i,n)
chk for anagram return true if found else
increment i till i+n<b.length.
code:
import java.util.*;
public class Anachk{
public boolean isAnagram(String s,String s1){//a and b in this function will have same length
char w1[]=s.toCharArray();
char w2[]=s1.toCharArray();
if(s.length()!=s1.length())
return false;
boolean ch=false;
HashMap<Character,Integer> chk=new HashMap<Character,Integer>();
for(int i=0;i<w1.length;i++){
char c=w1[i];
if(chk.containsKey(c))
chk.put(c, chk.get(c)+1);
else
chk.put(c, 1);
}
for(int i=0;i<w2.length;i++)
{
char c=w2[i];
if(chk.containsKey(c))
chk.put(c, chk.get(c)-1);
}
for(char c:chk.keySet()){
if(chk.get(c)==0)
ch=true;
else{
ch=false;
break;
}
}
return ch;
}
public void func(String a,String b){
if(0==a.length()||0==b.length()){
System.out.println("Null strings passed");
return;
}
if(a.length()>b.length()){
System.out.println("Error check length");
return;
}
int n=a.length();
int max=b.length();
int i;
boolean flag=false;
String tmp;
for(i=0;i<max;i++){
tmp="";
if(n>max)
break;
tmp=b.substring(i,n);
System.out.print(tmp+"\n");
flag=isAnagram(a,tmp);
n++;
if(flag==true)
break;
}
if(flag)
System.out.println("\nFound at(starting at): "+i+" ends at: "+(n-2));
else
System.out.println("Not found");
}
public static void main(String args[]){
Anachk z=new Anachk();
String a="xyz".toLowerCase();
String b="afdgZyxksldfm".toLowerCase();
z.func(a, b);
}
}
"""
Given two strings a and b, find whether any
anagram of string a is a sub-string of
string b. For eg:
if a = xyz and b = afdgzyxksldfm then the
program should return true.
"""
def kmp_table(W):
length = len(W)
if length == 1:
return [-1]
elif length == 2:
return [-1, 0]
elif length > 2:
T = [0] * length
T[0] = -1
T[1] = 0
pos = 2
cnd = 0
while pos < length:
if W[pos - 1] == W[cnd]:
cnd += 1
T[pos] = cnd
pos += 1
elif cnd > 0:
cnd = T[cnd]
else:
T[pos] = 0
pos += 1
return T
def kmp_search(S, W):
m = 0
i = 0
T = kmp_table(W)
while m + i < len(S):
if W[i] == S[m + i]:
if i == len(W) - 1:
return m
i += 1
else:
m += i - T[i]
if T[i] > -1:
i = T[i]
else:
i = 0
return len(S)
#include <iostream>
#include <map>
using namespace std;
void reset(map<char, pair<int, int> >& contents)
{
map<char, pair<int, int> >::iterator it;
for(it = contents.begin(); it != contents.end(); it++)
it->second.first = it->second.second;
}
bool containsAnagram(string word, string sentence)
{
map<char, pair<int, int> > contents;
int i;
for(i = 0; i < word.size(); i++)
{
pair<int, int>& counts = contents[word[i]];
counts.first = ++counts.second;
}
for(i = 0; i < sentence.size(); i++)
{
map<char, pair<int, int> >::iterator it = contents.find(sentence[i]);
while(it != contents.end())
{
(it->second.first)--;
if(i++ + 1 < sentence.size())
it = contents.find(sentence[i]);
else
return false;
}
bool foundAnagram = true;
for(it = contents.begin(); it != contents.end(); it++)
{
if(it->second.first != 0)
{
foundAnagram = false;
reset(contents);
break;
}
}
if(foundAnagram)
return true;
}
return false;
}
int main()
{
string word = "xyz";
string sentence = "11234yxabczyx12";
if(containsAnagram(word, sentence))
printf("'%s' contains anagram of '%s'\n", sentence.c_str(), word.c_str());
else
printf("'%s' does not contain anagram of '%s'\n", sentence.c_str(), word.c_str());
return 0;
}
public boolean hasAnagram(String s, String t) {
int[ ] windows = new int[256];
int[ ] record = new int[256];
int count = 0;
for (int i = 0; i < s.length(); i++)
record[s.charAt(i)]++;
for (int i = 0; i < s.length(); i++) {
if (windows[t.charAt(i)] < record[t.charAt(i)]) {
windows[t.charAt(i)]++;
count++;
}
}
if (count == s.length())
return true;
for (int i = 1; i + s.length() - 1 < t.length(); i++) {
char begin = t.charAt(i - 1);
char end = t.charAt(i + s.length() - 1);
if (windows[begin] > 0) {
windows[begin]--;
count--;
}
if (windows[end] < record[end]) {
windows[end]++;
count++;
}
if (count == s.length())
return true;
}
return false;
}
function findAnagram(sentence,value){
//validate parameters
if(!value || !sentence || value.length > sentence.length)
return false;
//create anagram as array
var anagram = a.split('').reverse();
var match_count = 0;
for(i = 0;i < sentence.length; i++){
//if char matches anagram char at the current match index increment counter
if(sentence[i] == anagram[match_count]){
match_count++;
if(match_count == anagram.length){
//match count matches anagram length, then found return true
return true;
}
}else
match_count = 0;
}
return false;
}
Seems like a lost war with so many answers but this may be a good solution. From what I think it will work in O(n) time.
public class AnagramUtils {
public static boolean isAnagramSubString(char[] smallString,char[] bigString){
if(smallString==null|| bigString==null){
return false;
}
if(smallString.length>bigString.length){
return false;
}
boolean returnVal = false;
Map <Character,Integer>m = new HashMap<>();
for(Character c:smallString){
if(m.containsKey(c)){
m.put(c,m.get(c)+1);
} else{
m.put(c, 1);
}
}
Map <Character,Integer>m2 = new HashMap<>();
for(Character c:bigString){
if(!m.containsKey(c) && !m2.isEmpty()){
m2 = new HashMap<>();
}else if(m.containsKey(c)){
if(m2.containsKey(c)){
m2.put(c, m2.get(c)+1);
}
else{
m2.put(c, 1);
}
if(m.equals(m2)){
returnVal = true;
}
}else{
if(!m2.isEmpty()){
m2 = new HashMap<>();
}
}
}
return returnVal;
}
Assume string a with smaller size and string b with larger size
Logic:
1. find all anagrams of a
2. check if each anagram is a substring of b
3. return true if find one, otherwise return false.
Code:
/*
* find if a string a and all its anagram is a substring of another string b
*/
public static boolean isAnagramsSubstring(String small, String large){
if(small==null||large==null) return false;
if(small.length()>large.length()) return false;
ArrayList<String> anagrams = findAnagrams(small);
for(String s: anagrams){
if(isSubstring(s, large)) return true;
}
return false;
}
private static boolean isSubstring(String a, String b){
for(int i=0; i<b.length(); i++){
if(b.charAt(i)==a.charAt(0)){
if(b.length()-i<a.length()) return false;
String part = b.substring(i, i+a.length());
if(part.equals(a)) return true;
}
}
return false;
}
private static ArrayList<String> findAnagrams(String str){
if(str==null) return null;
return findAnagrams(str, str.length()-1);
}
private static ArrayList<String> findAnagrams(String str, int curIndex){
ArrayList<String> result = new ArrayList<String>();
if(curIndex<0){
result.add("");
return result;
}
ArrayList<String> before = findAnagrams(str, curIndex-1);
for(String s : before){
for(int i=0; i<=s.length(); i++){
String newstr = insert(s, str.charAt(curIndex), i);
result.add(newstr);
}
}
return result;
}
private static String insert(String str, char c, int pos){
String left = str.substring(0,pos);
String right = str.substring(pos);
return left + c + right;
}
Moving window on B; O(b * a) ?
public boolean hasAnagramSubstring(String a, String b){
if(a == null || b == null || a.length() > b.length()){
return false;
}
int[] targetCounts = new int[256];
int[] windowCounts = new int[256];
for(int i = 0; i < a.length(); i++){
targetCounts[a.charAt(i)]++;
windowCounts[b.charAt(i)]++;
}
int length = a.length();
for(int endCursor = a.length() - 1; endCursor < b.length();){
boolean test = isAnagram(targetCounts, windowCounts);
if(test){
return true;
}
windowCounts[b.charAt(endCursor - length + 1)]--;
endCursor++;
if(endCursor >= b.length()){
break;
}else{
windowCounts[b.charAt(endCursor)]++;
}
}
return false;
}
private boolean isAnagram(int[] targetCounts, int[] windowCounts){
for(int i = 0; i < targetCounts.length; i++){
if(targetCounts[i] > 0 && targetCounts[i] != windowCounts[i]){
return false;
}
}
return true;
}
The answer to this depends whether it's intended to be case sensitive or not, are they alpha numeric only or any character, the size of the character (wide or single byte character), ...etc, but basically, this should work for the basic case of exact matching, and if we wanted we can modify it for any change in the requirement...
bool isContained(char* a, char* b) {
if (a == NULL || b == NULL){
return false;
}
int CharMap[sizeof(char) << 8];
ZeroMemory(CharMap, sizeof(CharMap));
for (char *c = &a[0]; c[0] != '\0'; c++) {
CharMap[c[0]-1]++;
}
for (char *c = &b[0]; c[0] != '\0'; c++) {
if (CharMap[c[0]-1] > 0) {
CharMap[c[0]-1]--;
}
}
for (int i = 0; i<_countof(CharMap); i++) {
if (CharMap[i] != 0) {
return false;
}
}
return true;
}
public boolean isAnagram(String _source1, String _source2)
{
int flag = 0, char_index = 0, counter = 0;
if(_source2.length() < _source1.length()){
return false;
}
char[] _stringchar = _source1.toCharArray();
char[] _tocheck = _source2.toCharArray();
for(char character : _stringchar)
{
char_index = character - 'a';
if((flag & (1 << char_index)) == 0)
flag |= (1 << char_index);
}
for(char toCheckcChar : _tocheck)
{
char_index = toCheckcChar - 'a';
if((flag & (1 << char_index)) > 0)
counter++;
else
counter = 0;
if(counter == _source1.length())
return true;
}
return false;
}
public boolean isAnagram(String _source1, String _source2)
{
int flag = 0, char_index = 0, counter = 0;
if(_source2.length() < _source1.length()){
return false;
}
char[] _stringchar = _source1.toCharArray();
char[] _tocheck = _source2.toCharArray();
for(char character : _stringchar)
{
char_index = character - 'a';
if((flag & (1 << char_index)) == 0)
flag |= (1 << char_index);
}
for(char toCheckcChar : _tocheck)
{
char_index = toCheckcChar - 'a';
if((flag & (1 << char_index)) > 0)
counter++;
else
counter = 0;
if(counter == _source1.length())
return true;
}
return false;
}
import java.util.*;
public class Anagram2 {
private boolean isAnagram(String s, String subStr) {
HashMap<Character, Integer> map1 = frequnecy(s);
HashMap<Character, Integer> map2 = frequnecy(subStr);
for (char c : s.toLowerCase().toCharArray()) {
if (map2.get(c) == null || map1.get(c) > (map2.get(c))) {
return false;
}
}
return true;
}
private HashMap<Character, Integer> frequnecy(String input) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
char[] ch = input.toLowerCase().toCharArray();
for (char c : ch) {
if (map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
return map;
}
public static void main(String[] args) {
Anagram2 testMap = new Anagram2();
boolean result1 = testMap.isAnagram("xyz", "afdgzxksldfm");
boolean result2 = testMap.isAnagram("abcdefg", "abcfedgsfdaf");
boolean result3 = testMap.isAnagram("a", "cdsgsdgsa");
boolean result4 = testMap.isAnagram("abc", "ccccccabbbbbbb");
System.out.print(result1);
System.out.print(result2);
System.out.print(result3);
System.out.print(result4);
}
}
public class Anagram2 {
private boolean isAnagram(String s, String subStr) {
if(s.length()>subStr.length())
return false;
HashMap<Character, Integer> map1 = frequnecy(s);
HashMap<Character, Integer> map2 = frequnecy(subStr);
for (char c : s.toLowerCase().toCharArray()) {
if (map2.get(c) == null || map1.get(c) > (map2.get(c))) {
return false;
}
}
return true;
}
private HashMap<Character, Integer> frequnecy(String input) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
char[] ch = input.toLowerCase().toCharArray();
for (char c : ch) {
if (map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
return map;
}
}
package google;
import org.junit.Test;
import java.util.HashSet;
import java.util.Set;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
public class SubStringAnagram {
@Test
public void test() {
assertTrue(hasAnagramAsSubstring("xyz".toCharArray(), "asdnzyxsa".toCharArray()));
assertFalse(hasAnagramAsSubstring("xyz".toCharArray(), "asdynzxsa".toCharArray()));
}
public static boolean hasAnagramAsSubstring(char[] a, char[] s) {
int[] occ = new int[26];
Set<Character> anagramLetters = new HashSet<>();
for (char ac : a) {
anagramLetters.add(ac);
occ[ac - 'a']++;
}
int[] cur = new int[26];
for (int i = 0; i < s.length; i++) {
char curLetter = s[i];
if (anagramLetters.contains(curLetter)) {
cur[curLetter - 'a']++;
}
if (i >= a.length) {
char letterToRemove = s[i - a.length];
if (anagramLetters.contains(letterToRemove)) {
cur[letterToRemove - 'a']--;
}
}
if (anagramLetters.contains(curLetter)) {
boolean found = true;
for (char l : anagramLetters) {
int pos = l - 'a';
if (occ[pos] != cur[pos]) {
found = false;
break;
}
}
if (found) {
return true;
}
}
}
return false;
}
}
Create char array of first variable and sort it and then convert it back to a string.
Now loop through 2nd variable each time picking number of character equal to length of first variable. Sort the picked characters and convert then back to a string and then compare with variable 1. As soon as there is a match break from for loop.
In C++, generate all the permutations of string a and check if they are substrings of b.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool check(string a, string &b){
sort(a.begin(), a.end());
do {
if (b.find(a) != string::npos)
return true;
}
while(next_permutation(a.begin(), a.end()));
return false;
}
int main(){
string a, b;
cin >> a >> b;
cout << check(a, b);
return 0;
}
algo:
1• Get XOR of current substring
2• XOR result with first few characters of text(few characters=length of substring)
3• Parse text and at each iteration remove last character and add new character till its end or xor==0
int anagramSubstring(char* text, char* sub)
{
int sublength=strlen(sub);
int i=0;
int xor=0;
int length=0;
while(i<sublength)
{
xor=xor ^ *(sub+i);
xor=xor ^ *(text+i);
i++;
}
length=strlen(text);
while(xor!=0 && i<length)
{
xor=xor ^ *(text+i);
xor=xor ^ *(text+i-sublength);
i++;
}
if(xor==0)
return 1;
else
return -1;
}
import java.util.Arrays;
public class whether_any_anagram_of_string_a_is_a_substring_of_string
{
public static void main(String []args)
{
whether_any_anagram_of_string_a_is_a_substring_of_string obj = new whether_any_anagram_of_string_a_is_a_substring_of_string();
String a="xyz";
String b="afdgyzxksldfm";
System.out.println(obj.substringAnagram(a,b));
}
private boolean substringAnagram(String a, String b)
{
boolean table[] = new boolean[256];
boolean orig_table[] = new boolean[256];
Arrays.fill(table,false);
Arrays.fill(orig_table,false);
for(int i=0;i<a.length();i++)
{
table[a.charAt(i)] = true;
orig_table[a.charAt(i)] = true;
}
int count = 0;
for(int j=0;j<b.length();j++)
{
if(table[b.charAt(j)]==true)
{
count++;
table[b.charAt(j)] = false;
if(count==a.length())
{
return true;
}
}
else if(count>0)
{
count = 0;
table = orig_table.clone();
}
}
return false;
}
}
O(n) solution in Java.
private boolean stringContainsAnagramOfOtherString() {
String a = "xyz";
String b = "afdgzyxksldfm"; // afdgyzxksldfm
boolean isMapRemoveStarted = false;
char[] achar = a.toCharArray();
char[] bchar = b.toCharArray();
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for (int i = 0; i < achar.length; i++) {
int ascii = (int) achar[i];
map.put(ascii,ascii);
}
for (int i = 0, j = 0; i < bchar.length && j < achar.length ; i++) {
int ascii = (int) bchar[i];
if(map.get(ascii)!=null){
isMapRemoveStarted = true;
System.out.println(map.get(ascii)+" ");
map.remove(ascii);
j++;
}else{
if(isMapRemoveStarted == true)
j++;
}
}
if(map.isEmpty()){
return true;
}else{
return false;
}
}
O(n) solution in Java.
private boolean stringContainsAnagramOfOtherString() {
String a = "xyz";
String b = "afdgzyxksldfm"; // afdgyzxksldfm
boolean isMapRemoveStarted = false;
char[] achar = a.toCharArray();
char[] bchar = b.toCharArray();
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for (int i = 0; i < achar.length; i++) {
int ascii = (int) achar[i];
map.put(ascii,ascii);
}
for (int i = 0, j = 0; i < bchar.length && j < achar.length ; i++) {
int ascii = (int) bchar[i];
if(map.get(ascii)!=null){
isMapRemoveStarted = true;
System.out.println(map.get(ascii)+" ");
map.remove(ascii);
j++;
}else{
if(isMapRemoveStarted == true)
j++;
}
}
if(map.isEmpty()){
return true;
}else{
return false;
}
}
O(n) solution in Java.
private boolean stringContainsAnagramOfOtherString() {
String a = "xyz";
String b = "afdgzyxksldfm"; // afdgyzxksldfm
boolean isMapRemoveStarted = false;
char[] achar = a.toCharArray();
char[] bchar = b.toCharArray();
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for (int i = 0; i < achar.length; i++) {
int ascii = (int) achar[i];
map.put(ascii,ascii);
}
for (int i = 0, j = 0; i < bchar.length && j < achar.length ; i++) {
int ascii = (int) bchar[i];
if(map.get(ascii)!=null){
isMapRemoveStarted = true;
System.out.println(map.get(ascii)+" ");
map.remove(ascii);
j++;
}else{
if(isMapRemoveStarted == true)
j++;
}
}
if(map.isEmpty()){
return true;
}else{
return false;
}
}
O(n) solution
private boolean stringContainsAnagramOfOtherString() {
String a = "xyz";
String b = "afdgzyxksldfm"; // afdgyzxksldfm
boolean isMapRemoveStarted = false;
char[] achar = a.toCharArray();
char[] bchar = b.toCharArray();
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for (int i = 0; i < achar.length; i++) {
int ascii = (int) achar[i];
map.put(ascii,ascii);
}
for (int i = 0, j = 0; i < bchar.length && j < achar.length ; i++) {
int ascii = (int) bchar[i];
if(map.get(ascii)!=null){
isMapRemoveStarted = true;
System.out.println(map.get(ascii)+" ");
map.remove(ascii);
j++;
}else{
if(isMapRemoveStarted == true)
j++;
}
}
if(map.isEmpty()){
return true;
}else{
return false;
}
}
import java.util.HashMap;
public class CheckAnagram {
public static void main(String[] args) {
String a = "xyz" ;
String b = "afdgzylxksldfm";
checkIfAnagramPresent(a,b);
}
public static void checkIfAnagramPresent(String a, String b)
{
HashMap<Character,Integer> stringMap = new HashMap<Character,Integer>();
int strlen = a.length();
for(int i=0;i<a.length();i++)
{
if(stringMap.containsKey(a.charAt(i)))
{
int count = stringMap.get(a.charAt(i));
stringMap.put(a.charAt(i), count +1);
}
else
{
stringMap.put(a.charAt(i), 1);
}
}
boolean isSubstring = checkForSubstring(stringMap,b,strlen);
if(isSubstring)
{
System.out.println("Substring contains an angram");
}
else
System.out.println("NOt an anagram");
}
public static boolean checkForSubstring(HashMap<Character,Integer> stringMap, String b, int len)
{
int counter =0;
int j = -1;
int k = -1;
for(int i=0;i<b.length();i++)
{
if(stringMap.containsKey(b.charAt(i)) )
{
j =i;
counter++;
if(j-k==1)
{
if(counter==len)
{
return true;
}
}
k =j;
}
}
return false;
}
}
import java.util.BitSet;
public class AnagramSubString {
public static void main(String args[]){
String str = "abcefghi";
String pat = "gefi";
BitSet p = new BitSet(256);
for(int i=0; i<pat.length();i++)
p.set((int)pat.charAt(i));
int np = pat.length();
for(int i=0; i<str.length()-np;i++){
BitSet s = new BitSet(256);
for(int j=0; j<pat.length();j++)
s.set((int)str.charAt(i+j));
if(s.equals(p)){
System.out.println("true");
return;
}
}
System.out.println("false");
}
}
Simple O(n) code in C++
bool is_anagram_wSubstr(string a, string b)
{
if(a.length() > b.length()) return false;
if(a.length() == 0) return true;
int counter[256];
memset(counter, 0, 256);
for(int i = 0 ; i < a.length(); i++){
counter[(int) a[i]] ++;
counter[(int) b[i]] --;
}
int ind, l = 0, h = a.length() - 1;
while(true){
for(ind = 0 ; ind < a.length() ; ind++)
if(counter[(int) a[ind]] != 0)
break;
if(ind == a.length()) return true;
counter[(int) b[l++]] ++;
if(++h > b.length() - 1) return false;
counter[(int) b[h]] --;
}
}
public static boolean anagram(String a, String b){
if(a.length() > b.length()){
return false;
}
HashMap<Character, Integer> h = new HashMap<Character, Integer>();
for(int i = 0; i<a.length(); i++){
if(h.get(a.charAt(i)) == null){
h.put(a.charAt(i),1);
}
else{
h.put(a.charAt(i),(Integer)h.get(a.charAt(i))+1);
}
}
for(int i = 0; i<b.length(); i++){
HashMap map = new HashMap<Character,Integer>(h);
int count = 0,right = i+1;
if(map.get(b.charAt(i)) != null){
count++;
map.put(b.charAt(i),(Integer)map.get(b.charAt(i)-1));
while(right <b.length()){
if(count == a.length()){
return true;
}
if(map.get(b.charAt(right)) == null || (Integer)map.get(b.charAt(right)) == 0 )
break;
else{
map.put(b.charAt(right),(Integer)map.get(b.charAt(right))-1);
right++; count++;
}
}
}
}
return false;
}
public static void main(String []args){
System.out.println(anagram("xyz","axcdefgzyasf"));
}
Using C++ set
//if any anagram of s1 is a substr of s2
bool anagram(string s1, string s2) {
set<char> contained;
for (int i = 0; i< s1.length(); i++) {
contained.insert(s1[i]);
}
for (int j = 0; j < s2.length(); j++) {
if(contained.find(s2[j]) != contained.end()) {
contained.erase(s2[j]);
}
if (contained.empty()) return true;
}
return false;
}
public class Anagram{
public boolean isAnagram(char[] text, char[] sub){
int i = 0;
int k = 0;
int m = sub.length -1;
while(i< sub.length && k < text.length){
if(sub[m-i] == text[k])
i++;
else{
i =0;
}
k++;
if( i == sub.length)
return true;
}
return false;
}
public static void main(String[] args){
String text = "afdgzyxksldfm";
String sub = "xyz";
Anagram ag = new Anagram();
System.out.println("Is Anagram "+ag.isAnagram(text.toCharArray(), sub.toCharArray()));
}
}
O(N) time solution and O(M) space given N is the size of B and M is the size of A. Implemented in Groovy with automated tests.
@Unroll
def "isAnagramSubstring(#str1, #str2) == #result"() {
expect:
isAnagramSubstring(str1, str2) == result
where:
str1 | str2 | result
"abc" | "abc" | true
"abc" | "cab" | true
"abc" | "def" | false
"abcdefabc" | "fed" | true
"abcdefabc" | "ghi" | false
"abcdeefabc" | "fed" | false
"abcdeefabc" | "fee" | true
"abc" | "" | true
"" | "" | true
"" | "def" | false
}
/*
abcdadefdabc | ddef
5--8
count | expected
d: 2 | 2
e: 1 | 1
f: 1 | 1
charactersCountMatching=2
*/
public boolean isAnagramSubstring(String str1, String str2) {
if(str1.length() < str2.length()) {
return false;
}
Map<Character, Integer> expectedCount = countCharacters(str2);
Map<Character, Integer> windowCount = new HashMap<Character, Integer>();
for(Character c : expectedCount.keySet()) {
windowCount.put(c, 0);
}
int start = 0;
int end = str2.length() - 1;
for(int i=0; i <= end; i++) {
char c = str1.charAt(i);
if(windowCount.get(c) != null) {
windowCount.put(c, windowCount.get(c)+1);
}
}
int charactersCountMatching = 0;
for(Character c : windowCount.keySet()) {
if(windowCount.get(c) == expectedCount.get(c)) {
charactersCountMatching++;
}
}
if(charactersCountMatching == expectedCount.size()) {
return true;
}
while(end+1 < str1.length()) {
start++;
end++;
char removedChar = str1.charAt(start-1);
if(windowCount.get(removedChar) != null) {
if(windowCount.get(removedChar) == expectedCount.get(removedChar)) {
charactersCountMatching--;
}
windowCount.put(removedChar, windowCount.get(removedChar)-1);
if(windowCount.get(removedChar) == expectedCount.get(removedChar)) {
charactersCountMatching++;
}
}
char addedChar = str1.charAt(end); //d
if(windowCount.get(addedChar) != null) {
if(windowCount.get(addedChar) == expectedCount.get(addedChar)) {
charactersCountMatching--;
}
windowCount.put(addedChar, windowCount.get(addedChar)+1);
if(windowCount.get(addedChar) == expectedCount.get(addedChar)) {
charactersCountMatching++;
}
}
if(charactersCountMatching == windowCount.size()) {
return true;
}
}
return false;
}
private Map<Character, Integer> countCharacters(String str) {
Map<Character, Integer> result = new HashMap<Character, Integer>();
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if(result.get(c) == null) {
result.put(c, 0);
}
result.put(c, result.get(c)+1);
}
return result;
}
bool function(string src, string dst)
{
bool hash[26] = {false};
for(int i=0;i<src.length();i++)
hash[(int)src[i]-97] = true;
int count = src.length();
for(int i=0;i<dst.length();i++)
{
if(!count)
return true;
if(hash[(int)dst[i]-97])
{
count--;
continue;
}
else
count = src.length();
}
return false;
}
public static boolean anagramString(String str1, String str2) {
if (str1 == null || str2 == null) return false;
if(str1.length() == 0 || str2.length() == 0) {
return false;
}
if(str1.equals(str2)) return true;
while(true) {
char ch = str1.charAt(0);
int len2 = str2.length();
int index2 = str2.indexOf(ch);
str1 = str1.substring(1);
if (index2 == -1) return false;
str2 = str2.substring(0, index2).concat(str2.substring(index2+1, len2));
if(str1.length() == 0 && str2.length() == 0) return true;
}
}
{public static boolean anagramString(String str1, String str2) {
if (str1 == null || str2 == null) return false;
if(str1.length() == 0 || str2.length() == 0) {
return false;
}
if(str1.equals(str2)) return true;
while(true) {
char ch = str1.charAt(0);
int len2 = str2.length();
int index2 = str2.indexOf(ch);
str1 = str1.substring(1);
if (index2 == -1) return false;
str2 = str2.substring(0, index2).concat(str2.substring(index2+1, len2));
if(str1.length() == 0 && str2.length() == 0) return true;
}
}}
public static boolean findIfAna(String a, String b){
int length = 0;
HashMap<Character,Integer> aHash = new HashMap<Character,Integer>();
List<Character> aList = new LinkedList<Character>();
for(int i =0;i<a.length();i++)
aHash.put(a.charAt(i),(int) a.charAt(i));
for(int i = 0;i<b.length();i++){
char cur = b.charAt(i);
if(aHash.containsKey(cur)){
aList.add(cur);
aHash.remove(cur);
length++;
if(length==a.length())
return true;
}
else if(aList.size()!=0){
char temp = aList.remove(0);
if(temp==cur)
aList.add(cur);
else{
aHash.put(temp,(int)temp);
length--;
}
}
}
return false;
}
My implementation is Python. There's a bit code repetition and I have some doubts about the efficiency. but it works
import re
def right_match(a,b):
""" checks if any character of a is in b right edge """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
try:
index = a.index(b[-1])
except:
return False;
return right_match(a[:index]+a[index+1:],b[0:-1])
def left_match(a,b):
""" checks if any character of a is in b left edge """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
try:
index = a.index(b[0])
except:
return False
return left_match(a[:index]+a[index+1:],b[1:0])
def special_contains(a,b):
""" finds if anagram of a contains in b """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
# step one - find all occurances of a[0]
# assuming a is alphanumeric character
occurances = [m.start() for m in re.finditer(a[0:1],b)]
# if that wasn't found then false for sure
if len(occurances) == 0 : return False
for index in occurances:
for i in range(len(a)):
if right_match(a[1:1+i],b[:index]) and left_match(a[1+i:],b[index+1:]) : return True
return False
Here's my implementation in Python. There's a bit code repetition and I have some doubts about the efficiency but it works.
import re
def right_match(a,b):
""" checks if any character of a is in b right edge """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
try:
index = a.index(b[-1])
except:
return False;
return right_match(a[:index]+a[index+1:],b[0:-1])
def left_match(a,b):
""" checks if any character of a is in b left edge """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
try:
index = a.index(b[0])
except:
return False
return left_match(a[:index]+a[index+1:],b[1:0])
def special_contains(a,b):
""" finds if anagram of a contains in b """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
# step one - find all occurances of a[0]
# assuming a is alphanumeric character
occurances = [m.start() for m in re.finditer(a[0:1],b)]
# if that wasn't found then false for sure
if len(occurances) == 0 : return False
for index in occurances:
for i in range(len(a)):
if right_match(a[1:1+i],b[:index]) and left_match(a[1+i:],b[index+1:]) : return True
return False
Here's my implementation in Python. There's a bit code repetition and I have some doubts about the efficiency but it works.
import re
def right_match(a,b):
""" checks if any character of a is in b right edge """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
try:
index = a.index(b[-1])
except:
return False;
return right_match(a[:index]+a[index+1:],b[0:-1])
def left_match(a,b):
""" checks if any character of a is in b left edge """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
try:
index = a.index(b[0])
except:
return False
return left_match(a[:index]+a[index+1:],b[1:0])
def special_contains(a,b):
""" finds if anagram of a contains in b """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
# step one - find all occurances of a[0]
# assuming a is alphanumeric character
occurances = [m.start() for m in re.finditer(a[0:1],b)]
# if that wasn't found then false for sure
if len(occurances) == 0 : return False
for index in occurances:
for i in range(len(a)):
if right_match(a[1:1+i],b[:index]) and left_match(a[1+i:],b[index+1:]) : return True
return False
import re
def right_match(a,b):
""" checks if any character of a is in b right edge """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
try:
index = a.index(b[-1])
except:
return False;
return right_match(a[:index]+a[index+1:],b[0:-1])
def left_match(a,b):
""" checks if any character of a is in b left edge """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
try:
index = a.index(b[0])
except:
return False
return left_match(a[:index]+a[index+1:],b[1:0])
def special_contains(a,b):
""" finds if anagram of a contains in b """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
# step one - find all occurances of a[0]
# assuming a is alphanumeric character
occurances = [m.start() for m in re.finditer(a[0:1],b)]
# if that wasn't found then false for sure
if len(occurances) == 0 : return False
for index in occurances:
for i in range(len(a)):
if right_match(a[1:1+i],b[:index]) and left_match(a[1+i:],b[index+1:]) : return True
return False
import re
def right_match(a,b):
""" checks if any character of a is in b right edge """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
try:
index = a.index(b[-1])
except:
return False;
return right_match(a[:index]+a[index+1:],b[0:-1])
def left_match(a,b):
""" checks if any character of a is in b left edge """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
try:
index = a.index(b[0])
except:
return False
return left_match(a[:index]+a[index+1:],b[1:0])
def has_anagram_substring(a,b):
""" finds if anagram of a contains in b """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
# step one - find all occurances of a[0]
# assuming a is alphanumeric character
occurances = [m.start() for m in re.finditer(a[0:1],b)]
# if that wasn't found then false for sure
if len(occurances) == 0 : return False
for index in occurances:
for i in range(len(a)):
if right_match(a[1:1+i],b[:index]) and left_match(a[1+i:],b[index+1:]) : return True
return False
Heres my implementation in python. a bit code repetition but it works:
import re
def right_match(a,b):
""" checks if any character of a is in b right edge """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
try:
index = a.index(b[-1])
except:
return False;
return right_match(a[:index]+a[index+1:],b[0:-1])
def left_match(a,b):
""" checks if any character of a is in b left edge """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
try:
index = a.index(b[0])
except:
return False
return left_match(a[:index]+a[index+1:],b[1:0])
def has_anagram_substring(a,b):
""" finds if anagram of a contains in b """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
# step one - find all occurances of a[0]
# assuming a is alphanumeric character
occurances = [m.start() for m in re.finditer(a[0:1],b)]
# if that wasn't found then false for sure
if len(occurances) == 0 : return False
for index in occurances:
for i in range(len(a)):
if right_match(a[1:1+i],b[:index]) and left_match(a[1+i:],b[index+1:]) : return True
return False
use this method in python as it does not have limit on int..
for a to z assign one prime number to each so there will be first 26 prime numbers assigned..now for string a do multiplication of prime number assigned to each character and now for that substring length try to do same in string b....if mul matches then return true
This algorithm consists of:
(1) checking the least frequent element of a in b
(2) find all the occurrences of this in b
(3) from each position look left and right to see if there are other contiguous characters from a
def decrement_counter(counter, key):
counter[key] -= 1
if counter[key] == 0:
del counter[key]
return counter
def contains_anagram(a, b):
if len(b) < len(a):
return False
a_counter, b_counter = Counter(a), Counter(b)
less_freq_char = min(a, key=lambda x: b_counter[x])
decrement_counter(a_counter, less_freq_char)
queue = deque()
for k, c in enumerate(b):
if c == less_freq_char:
queue.appendleft([k, k+1, a_counter])
while queue:
start, end, prev_counter = queue.pop()
num_elms = sum(prev_counter.values())
if start > 1 and b[start-1] in prev_counter:
if num_elms == 1:
return True
new_counter = decrement_counter(Counter(prev_counter), b[start-1])
queue.appendleft([start-1, end, new_counter])
if end < len(b) and b[end] in prev_counter:
if num_elms == 1:
return True
new_counter = decrement_counter(Counter(prev_counter), b[end])
queue.appendleft([start, end+1, new_counter])
return False
Will this one work...
Search for the occurrence of any character of string a in string b. Let this character be x.
If found, generate all anagrams of string a starting with x and check whether the same pattern is found in string b.
If found return true, else continue finding the next character
I am not sure if I am getting your solution right, the time complexity is O(k!n) right ?
where k = len(string a)
and n = len(string b)
your solution doesn't handle sol for below mentioned scenario:
String 1:
abc
String 2:
xncbabkl
As per ur sol:
i picked any char from string 1 lets say 'a'
and then found all the anagrams starting with 'a':
abc
acb
but both of the anagrams are not present in string 2
Your sol is missing checking 'cba' case.
No, my solution asks to look for any character of string a in string b..
From your example: characters in string a = {a,b,c}
While traversing string b, it detects character c and then generate two possible combinations - cab, cba and check whether the combinations are present in string b which will be found. So, will return true..
We can maintain the characters of string a in a hashmap so that search will take just O(1) time for each of the characters of string b.
oh ok....
you comment "any character of string a" made to think of this corner case which can be handled easily as you mentioned.
nice sol.
// 1. get all anagram strings of a
// 2. for each string in the anagram list, check if it is a substring of b
bool AnagramIsSubString(string a, string b)
{
string[] anagrams = GetAllAnagram(a);
bool found = false;
foreach (string anagram in anagrams)
{
if (b.IndexOf(anagram) != -1)
{
found = true;
break;
}
}
return found;
}
finding all anagram is expensive. use the other approach. Here is the c# code.
static bool AnagramIsSubstring(string a, string b)
{
if (a == null || b == null || a.Length > b.Length)
{
return false;
}
char[] achars = a.ToCharArray();
Array.Sort(achars);
string sorteda = new string(achars);
HashSet<char> aset = new HashSet<char>();
foreach (char c in achars)
{
aset.Add(c);
}
for (int i = 0; i < b.Length - a.Length + 1; ++i)
{
bool found = true;
for (int j = i; j < i + a.Length; ++j)
{
if (!aset.Contains(b[j]))
{
found = false;
break;
}
}
if (found)
{
char[] bchars = b.Substring(i, a.Length).ToCharArray();
Array.Sort(bchars);
string sortedb = new string(bchars);
if (string.Compare(sortedb, sorteda) == 0)
{
return true;
}
}
}
return false;
}
It is a trick question. First of all, one must realize that solutions like "produce all anagrams..." / search for each in string2 are damn slow, even if we use Boyer-More / Robin Karp and all good stuff. So just forget about this path. Instead, there is a linear solution.
Notice that if any contiguous part of s2 contains contains all characters from s1 and in the same amount, it is an anagram of s1 by definition.
So here is the algo:
This is algo O(N) (as dictionary operations are O(1))
Python implementation:
- Vladislav Kudelin October 07, 2017