Topcoder SRM 538 div2 easy "LeftOrRight"

問題: http://community.topcoder.com/stat?c=problem_statement&pm=11738&rd=14729 （要ログイン）

命令列が与えられる．右か左にゆくと命令するロボットがあり，与えられた命令列の順番で命令を実行する，右と左以外にもどちらでもすすめる記号が与えられる場合もある．命令を実行していく間に最初いた位置から最も遠い場所に移動するように命令を実行した時の距離を求める．

提出したやつはLL??RRRRR みたいなやつを警戒してたので再帰をして確実に答えだそうとしたらTLEくらった．（ ...?L?L?L?L?L... みたいなやつ）

実際は目一杯動けばいいから?をLRどちらか全部にしてしまえばいいやんという感じみたい．

間違い提出コード

public class LeftOrRight {
 
  public int maxDistance(String p) {
    return maxDist(p, 0, 0);
  }
 
  int max = 0;
 
  int maxDist(String p, int x, int h) {
    if (p.length() != 0) {
      String ss = p.substring(1);
      if (p.charAt(0) == '?') {
        if (h == 0) {
          maxDist(ss, x + 1, 1);
          maxDist(ss, x - 1, -1);
        } else {
          maxDist(ss, x + h, h);
        }
      } else if (p.charAt(0) == 'R') {
        maxDist(ss, x + 1, 0);
      } else {
        maxDist(ss, x - 1, 0);
      }
    }
    return max = Math.max(max, Math.abs(x));
  }
}

プラクティスで通ったコード

public class LeftOrRight {

	public int maxDistance(String p) {
		return Math.max(maxDist(p.replace('?', 'L'), 0, 0),
				maxDist(p.replace('?', 'R'), 0, 0));
	}

	int max = 0;

	int maxDist(String p, int x, int h) {
		if (p.length() != 0) {
			maxDist(p.substring(1), x + (p.charAt(0) == 'R' ? 1 : -1), 0);
		}
		return max = Math.max(max, Math.abs(x));
	}
}