Cracking the iOS Interview: Array Questions #2 - Check Permutation

Cracking the iOS Interview: Array Questions #2 - Check Permutation

Swift solutions to questions from Cracking the Coding Interview and other sources

Given two strings, write a method to decide if one is a permutation of the other.

The following is a Swift solution to question 1.2 in Cracking the Coding Interview

1 - Normal person approach (non-engineer)

If I had two words and somebody told me to see if both of those words were a permutation of one another, meaning they contained the same characters in different orders, then I would probably go through each string and count how many of each character there was. Then I would see if the counts for each character were the same. If they were, then they are permutations of each other.

2 - Code translation -- First pass

This sounds like a job for a dictionary with the key being the character and the value being the count, var permDict = [Character: Int](). I can go through the first word and set up the counts for each letter. Then as I go through the second word I can decrease the count value for each letter I see. After that, I can then loop through each value in the dictionary and see if any value is greater than 0. If all of the values equal 0, then that means there was the same amount of each letter in both words and they are permutations. If any letter has a value greater than 0, then they are not permutations.

func checkPermutation(s1: String, s2: String) -> Bool {
    // If the two strings have different lengths, then 
    // there is no possible way they be permutations
    guard s1.count == s2.count else {
        return false
    }

    var permDict = [Character: Int]()
    for char in s1 {
      if let count = permDict[char] {        
        permDict[char] = count + 1
      } else {
        permDict[char] = 1
      }
    }

    for char in s2 {
      if let count = permDict[char] {
        permDict[char] = count - 1
      } else {
        permDict[char] = -1
      }
    }

    for count in permDict.values where count != 0 {
       return false
    }
    return true
}

Looks pretty good, albeit a bit verbose. Runs in O(n) time, since we need to touch every character in both strings once.

3 - Another way

Another way we could do this is by using our knowledge that permutations contain the same amounts of the same characters. So we could just sort both of the strings and then compare them to see if they are equal and if they are, well then we're done.

func checkPermutation(s1: String, s2: String) -> Bool {
    // If the two strings have different lengths, then
    // there is no possible way they be permutations
    guard s1.count == s2.count else {
        return false
    }

    return s1.sorted() == s2.sorted()
}

This way is nice because of how simple it is. In just a few lines of codes we have solved the problem. Very simple to understand. The downside is that it's not as efficient. Using the built-in Swift sorted() function, we're going to have O(n*(log(n)) efficiency, which is not quite as good as O(n), but hey, this solution is so simple it just might justify it.

4 - Fim

Well, another question down. A couple of simple solutions to a fairly simple problem. Feel free to comment with any suggestions or questions about anything, both how I solved these problems as well as general Swift questions.