aboutsummaryrefslogtreecommitdiff
path: root/swap_adjacent_lr_string.c
blob: c7bbac9e66411835e2269a0464ee407f87deb9d5 (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
// 777. Swap Adjacent in LR String
#include "leetcode.h"

/*
 * in a string composed of 'L', 'R', and 'X' characters, like "RXXLRXRXL", a
 * move consists of either replacing one occurrence of "XL" with "LX", or
 * replacing one occurrence of "RX" with "XR". given the starting string 'start'
 * and the ending string 'end', return true if and only if there exists a
 * sequence of moves to transform 'start' to 'end'
 */

bool canTransform(char *start, char *end) {
  int c1 = 0, c2 = 0, i = 0, j = 0, n = strlen(start);
  for (i = 0; i < n; i++) {
    if (start[i] == 'X')
      c1++;
    if (end[i] == 'X')
      c2++;
  }
  if (c1 != c2)
    return false;
  i = j = 0;
  while (i < n && j < n) {
    if (start[i] == 'X')
      i++;
    else if (end[j] == 'X')
      j++;
    else {
      if ((start[i] != end[j]) || (start[i] == 'L' && i < j) ||
          start[i] == 'R' && i > j)
        return false;
      i++, j++;
    }
  }
  return true;
}

int main() {
  char *s1 = "RXXLRXRXL", *e1 = "XRLXXRRLX", *s2 = "X", *e2 = "L";
  printf("%d\n", canTransform(s1, e1)); // expect: 1
  printf("%d\n", canTransform(s2, e2)); // expect: 0
}