关于2337.Move-Pieces-to-Obtain-a-String 是否说反了？

[wisdompeak]

关于2337.Move-Pieces-to-Obtain-a-String 是否说反了？

[mingyEx]

这题我想了一上午，三种方法来搞都没跑通。

1.两边dp

要两边dp,记录每个L/R 经过滑动可以出现的位置，然后检查target[i]，如果是L就检查l[],否则检查r[],看对应位置是否可能相同。
但是对'_'的处理不正确，因为_是可能随着L的移动而变化的。

class Solution {
public:
  bool canChange(string s, string t) {
    string l(1, s.back()), r(1, s[0]);
    int sl = count(all(s), 'L');
    int sr = count(all(s), 'R');
    int tl = count(all(t), 'L');
    int tr = count(all(t), 'R');
    if (sl != tl || sr != tr)
      return false;

    //处理R
    for (int i = 1; i < s.size(); ++i)
      if (r.back() == 'R' && s[i] == '_')
        r += 'R';
      else
        r += s[i];
    //处理L
    for (int i = s.size() - 2; i >= 0; --i)
      if (l.back() == 'L' && s[i] == '_')
        l += 'L';
      else
        l += s[i];
    std::reverse(all(l));
    for (int i = 0; i < t.size(); ++i)
    {
      if (t[i] == 'L' && t[i] == l[i])continue;
      if (t[i] == 'R' && t[i] == r[i])continue;
      if (t[i] == '_'&&s[i]=='_') continue;
      return false;
    }
    return true;
  }
};

2.双指针

分别扫描L/R,要求它在s里出现的位置必须小于/大于 t里出现的位置

class Solution {
public:
  bool canChange(string s, string t) {
    int sl = count(all(s), 'L'),sr = count(all(s), 'R'),tl = count(all(t), 'L'),tr = count(all(t), 'R');
    if (sl != tl || sr != tr)return false;

    //r从左向右扫，t里存在的都挪动s.
    int r = 0;
    for (int i = 0; i < t.size(); ++i)
    {
      if (t[i] == 'R') {
        while (r < s.size() && s[r] != 'R')++r;
        if (r == t.size())return false;
        ++r;
      }
    }

    //l从右往左扫描，t里存在的都往前挪s
    int l = t.size() - 1;
    for (int i = t.size() - 1; i >= 0; --i)
    {
      if (t[i] == 'L') {
        while (l >= 0 && s[l] != 'L')--l;
        if (l == 0)return false;
        --l;
      }
    }
    //这个扫法也有问题，对于
    //"R_L_"
    //  "__LR"
    //  该是0 却返回1,双指针初试失败
    return true;
  }
};

跟您的答案可以说就差亿点点了。

[wisdompeak]

是的，文字解释里的这个逻辑写反了。刚改正了过来。谢谢提醒。