aboutsummaryrefslogtreecommitdiff
path: root/scramble_string.c
blob: e031211580682450ede7c92337fb115752390b67 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 87. Scramble String
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * string 's' can be scrambled to get string 't' using the following algorithm:
 * if length of string is 1, exit
 * if lenght of string is > 1:
 *   split string into two non-empty substrings at random index
 *   randomly decide to swap two substrings or to keep them in same order
 *   apply step 1 recursively
 * given two strings 's1' and 's2' of the same length, return true if 's2' is a
 * scrambled string of 's1', otherwise return false
 */

bool prune(char *s1, char *s2, int len) {
  int cnt[256] = {0};
  for (int i = 0; i < len; i++) {
    cnt[s1[i] - 'a']++;
    cnt[s2[i] - 'a']--;
  }
  for (int i = 1; i < len; i++)
    if (prune(s1, s2, i) && prune(s1 + i, s2 + i, len - i) ||
        prune(s1, s2 + len - i, i) && prune(s1 + i, s2, len - i))
      return true;
  return false;
}

bool isScramble(char *s1, char *s2) {
  int len = strlen(s1);
  if (!strncmp(s1, s2, len))
    return false;
  return prune(s1, s2, len);
}

int main() {
  char s1_1[] = {"great"}, s2_1[] = {"rgeat"};
  char s1_2[] = {"abcde"}, s2_2[] = {"caebd"};
  char s1_3[] = {"a"}, s2_3[] = {"a"};
  printf("%d\n", isScramble(s1_1, s2_1)); // expect: 1
  printf("%d\n", isScramble(s1_2, s2_2)); // expect: 0
  printf("%d\n", isScramble(s1_3, s2_3)); // expect: 1
}