Determine whether one string is a permutation of the other

Question 1.3 of Cracking the Coding Interview:

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

Two strings are a “permutation” if they contain the same distribution of characters. So one solution is to build this distribution for each string, and check whether those distributions are the same. For example, "hello" and "ehlol" are permutations of each other, because they both have the same character distribution, {e: 1, h: 1, l: 2, o: 1}.

Here’s a solution in C. It represents the character distribution as an int[255], where distrib[c] gives the count of the character c.

#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

void char_distrib(char* s, int distrib[]) {
  for (int i = 0; s[i] != '\0'; i++) {
    distrib[s[i]]++;
  }
}

bool is_permutation(char* a, char* b) {
  int* a_distrib = calloc(255, sizeof(int));
  int* b_distrib = calloc(255, sizeof(int));
  char_distrib(a, a_distrib);
  char_distrib(b, b_distrib);
  for (int i = 0; i < 256; i++) {
    if (a_distrib[i] != b_distrib[i]) return false;
  }
  return true;
}

void test(char* a, char* b, bool output) {
  assert(is_permutation(a,b) == output);
}

int main(int argc, char** argv) {
  test("hello", "ehlol", true);
  test("hell", "ehlol", false);
  test("", "", true);
  return 0;
}

This runs in O(len(a)+len(b)) and uses constant memory. This is optimal, because we at least have to look at every character, which is already linear time.

The other “obvious” solution is to sort both strings and check they’re the same. But this is less efficient, and harder to implement in C.

This page copyright James Fisher 2020. Content is not associated with my employer. Found an error? Edit this page.

Jim Fisher

CV

Speaking

Blogroll

RSS

Granola