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.

About these ads

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;
    }
    
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 612 other followers

%d bloggers like this: