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.
With Vidrio
With generic competitor
More by Jim
- Your syntax highlighter is wrong
- Granddad died today
- The Three Ts of Time, Thought and Typing: measuring cost on the web
- I hate telephones
- The sorry state of OpenSSL usability
- The dots do matter: how to scam a Gmail user
- My parents are Flat-Earthers
- How Hacker News stays interesting
- Project C-43: the lost origins of asymmetric crypto
- The hacker hype cycle
- The inception bar: a new phishing method
- Time is running out to catch COVID-19
- A probabilistic pub quiz for nerds
- Smear phishing: a new Android vulnerability
Tagged #ctci, #programming, #c. All content copyright James Fisher 2020. This post is not associated with my employer. Found an error? Edit this page.