javaで文字列を再帰的に反転させる方法【Leetcode】

Question

java初学者です。leetcodeというサイトで再帰の学習をしていたのですが、解法として記載されていたコードの理解がトレースしても理解できなかったため、ご助言をいただきたいです。

Reverse String

文字列を再帰的に反転させる方法の一例として、以下がSolutionとして記載されていました。

class Solution {
  public void helper(char[] s, int left, int right) {
    if (left >= right) return;
    char tmp = s[left];
    s[left++] = s[right];
    s[right--] = tmp;
    helper(s, left, right);
  }

  public void reverseString(char[] s) {
    helper(s, 0, s.length - 1);
  }
}

このコードを読んだだけでは理解できなかったため、トレースしようと思い、
例えば"hello"という文字列で考えた場合、sははじめ

0 1 2 3 4
h e l l o

で、

left = 0
right = 4

となるかと思います。ここからコードの通り処理を追って行くと、

tmp = h
s[left++] = s[1] = o
s[right--] = s[3] = h

となり、この時点で文字列が

0 1 2 3 4
h o l h o

となる、と解釈したのですが、これではs[1]のeの文字が上書き？されているので、その後反転した文字列を形成できないのでは？と思いました。

さらに再帰の処理をすすめた場合、

helper(s , 1, 3)
tmp = o
s[2] = h
s[2] = o

となり、s[2]に対して処理を2回することになるもの不可解で、混乱しております。

トレース方法や処理の解釈が違っているのだと思いますが、ご指摘をお願いします。

Answer 1

left = 0

right = 4

となるかと思います。ここからコードの通り処理を追って行くと、

tmp = h

s[left++] = s[1] = o
s[right--] = s[3] = h

となり、

演算子が後置されているので、
s[left++] ⇒ s[0] = o
s[right--] ⇒ s[4] = h です。

---

次のように書けば少しだけ素直になるように思います。

if (left >= right) return;
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
helper(s, left+1, right-1);

Comments

[macaroni323]

即座のご回答ありがとうございました！理解できました。

Answer 2

変数の後にある++,--は後置インクリメント、後置デクリメントと呼び、それぞれ数値を1増やす、1減らす演算子ですが、その演算子を書いたところに使われる値は変化する前の値です。
最初に呼び出されるときはこうなります。

    char tmp = s[left];  //tmpという変数にs[0],つまり'h'が代入される
    s[left++] = s[right];  //s[0]にs[4],つまり'o'代入。この後でleftが1に変化。
    s[right--] = tmp;  //s[4]にtmpの'h'代入。この後でrightが3に変化。
    helper(s, left, right);  //hepler(s, 1, 3)の呼び出し

Comments

[macaroni323]

ご回答ありがとうございました！

Answer 3

tmp = h

s[left++] = s[1] = o
s[right--] = s[3] = h
となり、この時点で文字列が
0 1 2 3 4
h o l h o

left++ と right-- は後置のため, 加減算されるのは評価後です.

tmp = h
s[left++] = s[0] ← o
s[right--] = s[4] ← h
となり、この時点で文字列が
0 1 2 3 4
o e l l h

Comments

[macaroni323]

ご回答ありがとうございました！