Skip to content

777. Swap Adjacent in LR String

  • Time: $O(n)$
  • Space: $O(1)$
 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
class Solution {
 public:
  bool canTransform(string start, string end) {
    if (removeX(start) != removeX(end))
      return false;

    int i = 0;  // start's index
    int j = 0;  // end's index

    while (i < start.length() && j < end.length()) {
      while (i < start.length() && start[i] == 'X')
        ++i;
      while (j < end.length() && end[j] == 'X')
        ++j;
      if (i == start.length() && j == end.length())
        return true;
      if (i == start.length() || j == end.length())
        return false;
      if (start[i] == 'L' && i < j)
        return false;
      if (start[i] == 'R' && i > j)
        return false;
      ++i;
      ++j;
    }

    return true;
  }

 private:
  string removeX(const string& s) {
    string t = s;
    t.erase(remove(begin(t), end(t), 'X'), end(t));
    return t;
  }
};

 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
class Solution {
  public boolean canTransform(String start, String end) {
    if (!start.replace("X", "").equals(end.replace("X", "")))
      return false;

    int i = 0; // start's index
    int j = 0; // end's index

    while (i < start.length() && j < end.length()) {
      while (i < start.length() && start.charAt(i) == 'X')
        ++i;
      while (j < end.length() && end.charAt(j) == 'X')
        ++j;
      if (i == start.length() && j == end.length())
        return true;
      if (i == start.length() || j == end.length())
        return false;
      if (start.charAt(i) == 'L' && i < j)
        return false;
      if (start.charAt(i) == 'R' && i > j)
        return false;
      ++i;
      ++j;
    }

    return true;
  }
}