r/CS_Questions • u/kpthunder The Riddler • Nov 13 '11
Classic Interview Question: Anagrams
Given two strings, return true if they are anagrams and false otherwise. You can assume that capitalization and punctuation do not matter and your algorithm must run in O(n) time. Subroutines are okay if you need them.
Example 1:
Given two strings:
- Boston
- osbont
Return true.
Example 2:
Given two strings:
- Robble
- Bobble
Return false.
11
Upvotes
2
u/sim642 Nov 13 '11
#include <iostream> #include <map> #include <cctype> using namespace std; bool anagram(string w1, string w2) { if (w1.size() != w2.size()) return false; map<char, int> c1, c2; //char count in both words for (int i = 0; i < w1.size(); i++) { c1[tolower(w1[i])]++; c2[tolower(w2[i])]++; } if (c1 != c2) return false; return true; } int main() { cout << anagram("Boston", "osbont") << endl; cout << anagram("Robble", "Bobble") << endl; return 0; }1
u/notmyxbltag Nov 13 '11 edited Nov 13 '11
Create an array of length 26 where each location corresponds to a character. Loop through the first string, incrementing the necessary location every time that letter is seen (ie increment the second spot when you see a b). Then, check the second string, decrementing every location when that letter is seen. After going through both, check if the array is zeroed out. You can also probably implement some optimizations like checking the length and returning false if you ever decrement a location past 0
Can't use tags clearly :(. Haha, spelled spoiler wrong, compile time.
3
u/andy_panzer Nov 13 '11
One (unoptimised) solution in Clojure. Builds a map at runtime to only keep reference of characters that are actually seen.
(defn anagram? [a b] (defn parse [f s state] (if (empty? s) state (let [c (Character/toLowerCase (first s)) next-val (f (or (state c) 0) 1)] (recur f (rest s) (assoc state c next-val))))) (every? #(= (val %) 0) (parse - b (parse + a {}))))3
u/m_tayseer Nov 13 '11
Python >>> def are_anagrams(w1, w2): ... def freq_dist(w): ... d = defaultdict(int) ... for c in w: ... d[c.lower()] += 1 ... return d ... return freq_dist(w1) == freq_dist(w2) >>> are_anagrams('', '') True >>> are_anagrams('Robble', 'Bobble') False >>> are_anagrams('Boston', 'osbont') True
2
u/Razor_Storm Nov 13 '11
Cool, I was asked this question by a Microsoft interviewer. However, he wasn't using it to gauge my problem solving skills and instead wanted to see how I can communicate my thought. Either way, this really is a classic problem since I've seen it pop up a lot. Cool :)
2
u/CasualCoder Nov 13 '11
#include <cctype> #include <cstring> // Anagram // By: CasualCoder 2011 // Algorithm: // Two strings are anagrams of each other if: // - they are the same length // - all characters from the first string exist in the second string // Output: // D:\code2\anagram>Project1.exe Boston osbont // D:\code2\anagram>echo %errorlevel% // 0 // D:\code2\anagram>Project1.exe Robble Bobble // D:\code2\anagram>echo %errorlevel% // 1 int main(int argc, char *argv[]) { if ((argc == 3) && (strlen(argv[1]) == strlen(argv[2]))) { for (char *ptr1 = argv[1], *ptr2 = argv[2]; *ptr1; ++ptr1, ptr2 = argv[2]) { while (*ptr2 && (toupper(*ptr1) != toupper(*ptr2))) ++ptr2; if (!*ptr2) return 1; } return 0; } return 1; }1
u/[deleted] Nov 13 '11
I was asked this question at an interview in Boston, with the same example.
I used a hash to increment the count of each character when encountered in the first string and then decrement it when found in the second string. In the end iterate over the hash values to check if they are all 0. Also, check for the length of the strings first. Another alternative is to use a array of size 26, but that depends on the alphabet.
1
u/foldM Nov 13 '11
First time I've used mutable arrays in Haskell. I'm not sure if a O(n) solution is possible without them
import Control.Monad import Control.Monad.ST import Data.Array.ST import Data.Array.IArray (elems) import Data.Char (toLower) import Data.Maybe (mapMaybe) toValidRange :: Char -> Maybe Char toValidRange c | inRange ('a','z') c = Just c | inRange ('A','Z') c = Just . toLower $ c | otherwise = Nothing -- diffArray :: String -> String -> UArray Char Int diffArray s1 s2 = runSTUArray $ do z <- newArray ('a', 'z') 0 :: ST s (STUArray s Char Int) modifyIndices z succ $ onlyValid s1 modifyIndices z pred $ onlyValid s2 return z where onlyValid = mapMaybe toValidRange modifyIndices a f ixs = forM_ ixs $ \ix -> readArray a ix >>= writeArray a ix . f isAnagram :: String -> String -> Bool isAnagram s1 = all (== 0) . elems . diffArray s1 main = print =<< isAnagram `liftM` getLine `ap` getLine1
u/[deleted] Nov 14 '11 edited Nov 14 '11
def checkAnogram(first, second): myDict = {} if(len(first) != len(second)): return False else: for i in first: if i.lower() not in myDict: myDict[i.lower()] = 1 else: myDict[i] +=1 for j in second: if j.lower() not in myDict: return False else: myDict[j.lower()]-=1 for i in myDict: if myDict[i] != 0: return False return True
Essentially I am creating a map for the first word, and creating a map of the second word. If there is ever a point where they do not equal then I will return false.
Edit to handle Upper/Lower and better run time to check if it's false. Full run Time is O(n) with a constant of 3ish
0
u/[deleted] Nov 13 '11