Check Permutation¶

This page goes over the question on strings “Check Permutation” in the book Cracking the Coding Interview, which we covered at our first “Interview Prep” meeting in Fall 2019. Try solving it yourself before reading the example solution below.

Check Permutation: Given two strings, write a method to decide if one is a permutation of another.

In other words: check if one word can be the other by rearranging the letters.

-------------------------------------------------------------------------

Show/Hide Solution

A “permutation”, or an “anagram” when referring to words, is a group of things that is the same as another group of things, except the things are rearranged. For example, “listen” is an anagram of “silent” because the letters in “listen” can form the word “silent”.

One way to solve this is by counting how many of each letter there are, and checking if those are the same between words. The easiest way to do that would be with a Dictionaries, although it can also be done with an array (Preferred Arrays). The examples below use this, and they have a linear time complexity, or O(n). See this page for that: Time and Space Complexities.

Another way is by sorting the characters in the word and then comparing the strings. This is sort of doing the same thing, but in a slower way. Typically the Native Sort can be used for that.

#include <iostream>
#include <unordered_map>
using namespace std;

bool anagramCheck(string one, string two){
  unordered_map<char, int> wordOne;
  unordered_map<char, int> wordTwo;

  for(int i = 0; i < one.length(); i++)
    wordOne[one[i]]++;
  for(int i = 0; i < two.length(); i++)
    wordTwo[two[i]]++;

  return wordOne == wordTwo;
}

int main() {
  cout << boolalpha;
  cout << anagramCheck("alucard", "dracula") << endl;
  cout << anagramCheck("eleven plus two", "twelve plus one") << endl;
  cout << anagramCheck("absolutely not", "an anagram") << endl;
}

using System.Collections.Generic;
class Program {
  static bool anagramCheck(string wordOne, string wordTwo){
    Dictionary<char, int> dictOne = makeDict(wordOne);
    Dictionary<char, int> dictTwo = makeDict(wordTwo);
    if(dictOne.Count != dictTwo.Count)
      return false;
    else
      foreach(KeyValuePair<char, int> entry in dictOne){
        if(dictOne[entry.Key] != entry.Value)
          return false;
      }
    return true;
  }
  static Dictionary<char, int> makeDict(string word){
    Dictionary<char, int> dict = new Dictionary<char, int>();

    for(int i = 0; i < word.Length; i++)
      if(dict.ContainsKey(word[i]))
        dict[word[i]]++;
      else
        dict[word[i]] = 1;

    return dict;
  }
  static void Main(string[] args) {
    System.Console.WriteLine(anagramCheck("alucard", "dracula"));
    System.Console.WriteLine(anagramCheck("eleven plus two", "twelve plus one"));
    System.Console.WriteLine(anagramCheck("absolutely not", "an anagram"));
  }
}

import java.util.*;
public class anagramCheck {
  public static Boolean checkAnagram(String wordOne, String wordTwo) {
    Map<Character, Integer> dictOne = makeDict(wordOne);
    Map<Character, Integer> dictTwo = makeDict(wordTwo);

    return dictOne.equals(dictTwo);
  }
  public static Map<Character, Integer> makeDict(String word){
    Map<Character, Integer> dict = new HashMap<Character, Integer>();

    for(int i = 0; i < word.length(); i++)
      if(dict.containsKey(word.charAt(i)))
        dict.put(word.charAt(i), dict.get(word.charAt(i)) + 1);
      else
        dict.put(word.charAt(i), 1);

    return dict;
  }
  public static void main(String[] args) {
    System.out.println(checkAnagram("alucard", "dracula"));
    System.out.println(checkAnagram("eleven plus two", "twelve plus one"));
    System.out.println(checkAnagram("absolutely not", "an anagram"));
  }
}

function anagramCheck(wordOne, wordTwo){
  var dictOne = makeDict(wordOne);
  var dictTwo = makeDict(wordTwo);

  if(Object.keys(dictOne).length !== Object.keys(dictTwo).length)
    return false;
  Object.keys(dictOne).forEach( function(key){
    if(dictOne[key] !== dictTwo[key])
      return false;
  });
  return true;
}
function makeDict(word){
  var dict = {};
  for(var i = 0; i < word.length; i++){
    if(dict[word[i]] !== undefined)
      dict[word[i]] += 1;
    else
      dict[word[i]] = 1;
  }
  return dict;
}

console.log(anagramCheck("alucard", "dracula"));
console.log(anagramCheck("eleven plus two", "twelve plus one"));
console.log(anagramCheck("absolutely not", "an anagram"));

def anagramCheck(wordOne, wordTwo):
  return makeDict(wordOne) == makeDict(wordTwo)

def makeDict(word):
  wordDict = {}
  for char in word:
    if char in wordDict:
      wordDict[char] += 1
    else:
      wordDict[char] = 1
  return wordDict

print(anagramCheck("alucard", "dracula"))
print(anagramCheck("eleven plus two", "twelve plus one"))
print(anagramCheck("absolutely not", "an anagram"))

func anagramCheck(_ wordOne: String,_ wordTwo: String) -> Bool{
  let dictOne = makeDict(wordOne)
  let dictTwo = makeDict(wordTwo)

  return dictOne == dictTwo;
}
func makeDict(_ word: String) -> [Character : Int]{
  var dict = [Character : Int]()
  for char in word{
    if dict[char] != nil{
      dict[char]! += 1
    }
    else{
      dict[char] = 1
    }
  }
  return dict
}

print(anagramCheck("alucard", "dracula"))
print(anagramCheck("eleven plus two", "twelve plus one"))
print(anagramCheck("absolutely not", "an anagram"))

Notes