## Anagrams Within Words

### February 21, 2014

We have a little programming puzzle today:

Given two words, determine if the first word, or any anagram of it, appears in consecutive characters of the second word. For instance, cat appears as an anagram in the first three letters of actor, but car does not appear as an anagram in actor even though all the letters of car appear in actor.

Your task is to write a function to determine if an anagram is present in a word. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisement

Pages: 1 2

### 13 Responses to “Anagrams Within Words”

1. some posiblidades were missing, the ideal thing would be with a ringlet but I feel sleepy and want to sleep, greetings

def check_anagr(anagram, string):
lib = {}
string = str(string)
for x in range(3):
lib[x] = string[x:x+1]
posibilidades = [‘110’, ‘100’, ‘000’, ‘001’, ‘011’, ‘111’, ‘220’,’200′, ‘222’,’211′, ‘112’, ‘002’,’022′, ‘020’, ‘012’, ‘112’, ‘021’, ‘212’, ‘221’, ‘121’, ‘120’, ‘102’]
for i in posibilidades:
r = i
var = ‘{}{}{}’.format(lib[int(r[0])], lib[int(r[1])], lib[int(r[2])])
if anagram == var:
return True
else:
return False

>>> check_anagr(‘cat’, ‘actor’)
True
>>> check_anagr(‘car’, ‘actor’)
False
>>>

2. Paul said

In Python.

```from collections import Counter
from itertools import islice, tee, izip

def update(counter, a, b):
'replace a by b in Counter'
counter[b] += 1
counter[a] -= 1
if counter[a] == 0:
del counter[a]

def anagram(first, second):
ita, itb = tee(iter(second))
target = Counter(first)
actual = Counter(islice(itb, len(first)))
if target == actual:
return True
for a, b in izip(ita, itb):
update(actual, a, b)
if target == actual:
return True
return False

print anagram("trel", "appletree") # True
print anagram("reel", "appletree") # False
print anagram("diep", "parallellepipedum") # True
print anagram("dier", "parallellepipedum") # False
```
3. /* header files */
#include // get access to printf() and scanf()
#include // get access to boolean values
#include // get access to strlen()

/* function prototypes */
bool searchForChar(char c, char* small_word);
bool isAnagram(char* small_word, char* large_word);

/* function definitions */
int main(void)
{
char* small_word;
char* large_word; // set variable for the 2 words

printf(“Small word is: “); // ask for the small one
scanf(“%s”, small_word);

printf(“Large word is: “); // ask for the large one
scanf(“%s”, large_word);

char* result;

if (isAnagram(small_word, large_word)) result = “match!”; // check and print the result
else result = “no matching!”;

printf(“%s\n”, result);
}

/* for example, we have “cat” and “actor”.
we are going to divide “actor” into triplets like that (act, cto, tor)
then we will test matching between each triplet and the small word
if matching present our function will return (true) */

bool isAnagram(char* small_word, char* large_word)
{
int len_of_small = strlen(small_word); // get the length of the small word

int len_of_large = strlen(large_word); // get the length of the large one

int counter; // set a counter to check full matching

for (int i = 0; i <= len_of_large – len_of_small; i++) // iterate over the large word till the index before the end by the length of the small one
{
counter = 0; // set the counter at zero

for (int j = i; j < i + len_of_small; j++) // iterate over the large word from the current index (i) for the length of the small
{
if(searchForChar(large_word[j], small_word)) counter++; // check if the current char is present in the small word and if so update counter
}

if (counter == len_of_small ) return true; // if counter reach the length of the small word return true
}

return false; // else, return false
}

bool searchForChar(char c, char* small_word)
{
for (int i = 0, len = strlen(small_word); i < len; i++) // iterate over the small word and see if the char sent from prev. function exists in it
{
if (small_word[i] == c)
{
return true; // if so, return true
}
}

return false; // else, return false
}

4. GyrosOfWar said

Lazy solution in Clojure using math.combinatorics/permutations:
http://pastebin.com/NHwcLt4M

5. PHP Solution: http://pastebin.com/1mur1TUs

/anagram.php
Enter anagram: cat
Enter word: actor
bool(true)

./anagram.php
Enter anagram: car
Enter word: actor
bool(false)

./anagram.php
Enter anagram: top
Enter word: boptin
bool(true)

./anagram.php
Enter anagram: butt
Enter word: tubtin
bool(true)

6. Toxic said

In Java code:

public static boolean testAnagram(String originalWord, String containedWord)
{
char [] first = originalWord.toCharArray();//Get the first word and store it into a character array.
char [] second = containedWord.toCharArray();//Get the second word and store it into a character array.
int [] index = new int[second.length];//An int array that stores the index of matching letters contained in the original array.
int counter = 0;//Keep count of the index storage position.

//Compare each character of both words.

for(int i = 0; i < second.length; i++)
{
for(int j = 0; j < first.length; j++)
{
if(second[i] == first[j])
{
index[counter] = j; //Store matching letters.
counter++; //Increment the index storage position.
break;//Break for loop.
}
}
}

if(counter < second.length)return false;//If not all letters were found.

//get the distance between the indices which should be no more than one
//less than the contained word length (to qualify as an anagram)

for(int i = 0; i < index.length; i++)
{
for(int j = 0; j = second.length) return false;
}
}

//If all qualifications are met.
return true;
}

7. vibhumishra007 said

hello Friends
Solution in c—->

#include
#include
#include
#include
char arr1[4];
int flag=0;
void swap(char*,char*);
void permut(char*,int ,int);
void swap(char *x,char *y)
{
char temp;
temp=*x;
*x=*y;
*y=temp;
}
void permut(char *a,int i,int n)
{
int j;
if(i==n)
{
char *ptr=NULL;
ptr=strstr(a,arr1);
if(ptr!=NULL)
{
printf(“true”);
flag=1;
getch();
exit(0);
}
}
else
{
for(j=i;j<=n;j++)
{
swap((a+i),(a+j));
permut(a,i+1,n);
swap((a+i),(a+j));//backtarck
}
}
}

void main()
{
strcpy(arr1,"cea");
char arr[]="actor";
clrscr();
permut(arr,0,4);
if(flag==0)
printf("false");
getch();
}

8. […] implemented the Anagrams Within Words programming puzzle from Programming Praxis in Python, a language I haven’t used since my […]

9. matthew said

A late entry here in C++: use a multiset (possibly with negative element counts) to store the difference between target characters and the characters in the string being searched. Incrementally keep track of the size of the difference and output the string offset if difference is zero.

```#include <stdio.h>
#include <string.h>
#include <assert.h>

template <typename Element, int N>
class MSet {
public:
MSet() : elems(), sz(0) {}
void add(Element c) {
if (++elems[c] > 0) sz++;
else sz--;
}
void sub(Element c) {
if (--elems[c] < 0) sz++;
else sz--;
}
int size() const { return sz; }
private:
int elems[N];
int sz;
};

void check (const char *s, const char *t)
{
int slen = strlen(s);
int tlen = strlen(t);
assert(slen <= tlen);
printf("'%s' '%s':",s,t);
MSet<unsigned char, 256> mset;
for(int i = 0; i < slen; i++) {
mset.sub(s[i]); mset.add(t[i]);
}
if (mset.size() == 0) printf(" %d", 0);
for(int i = slen; i < tlen; i++) {
mset.sub(t[i-slen]); mset.add(t[i]);
if (mset.size() == 0) printf(" %d", i-slen+1);
}
printf("\n");
}

int main()
{
check("","");
check("","foo");
check("foo","foooof");
check("foo","foofoo");
check("bar","foobaz");
check("foo","barfoo");
check("foo","foo foo");
check("fff","fffffff");
}
```
10. A not so efficient solution in Python:

```import itertools

def anagram(a, b):
for p in itertools.permutations(a, len(a)):
if b.find(''.join(p)) >= 0:
return True
return False

for w1, w2 in (('cat', 'actor'), ('car', 'actor')):
print("%s %s -> %s" % (w1, w2, anagram(w1, w2)))
```
11. rock321987 said

Here is O(nk) solution using Sliding window algo..i was asked this question in amazon..i was not able to solve it there..is there more efficient approach??

```#include <cstdio>
#include <string>
#include <iostream>

using namespace std;

int calc(string arr, string str)
{
if (arr.length() > str.length()) {
return -1;
}

int length = arr.length(), freqarr[255] = {0}, freqstr[255] = {0};

for (int i = 0;i < length;i++) {
freqarr[arr.at(i)]++;
freqstr[str.at(i)]++;
}

for (int i = 0;i <= str.length() - length;i++) {
int flag = 0;

for (int j = i;j < i + length;j++) {
char tmp = str.at(j);
//printf("%c\n", tmp);
if (freqarr[tmp] >= freqstr[tmp]) {

} else {
flag = 1;
break;
}
}

if (flag == 0) {
return i;
} else {
if (i != str.length() - length) {
freqstr[str.at(i)]--;
freqstr[str.at(i + length)]++;
}
}
}
return -1;
}

int main()
{
while (1) {
string arr, str;
cin >> arr >> str;

int x = calc(arr, str);

if (x == -1) {
printf("Not Found\n");
} else {
printf("Found\n");
}
}

return 0;
}

```