今更聞けない。Javascript、Pythonで文字列を逆順にするアルゴリズムとは?
今回は、とても有名な問題を解いてみましょう。この問題は、エンジニアの面接でもよく出題されることがありますよ。
問題は簡単です。与えられた文字列を逆順にする方法を見つけましょう。例えば、文字列「hello」を「olleh」に変換することが目標です。
まずは、単純な解法を見てみましょう。以下のJavaScriptのコードをご覧ください。
単純な解法
function reverseString(s) {
var reverseString = "";
for (let i = s.length - 1; i >= 0; i--) {
reverseString += s[i];
}
return reverseString;
}
この方法では、与えられた文字列を最後の文字から順に取り出して、新しい文字列に逆順に追加していきます。これにより、文字列が逆になります。
次に、再帰を使った解法を見てみましょう。以下のコードをご覧ください。
再帰版
function reverseStringRec(str) {
if (str.length <= 1) return str;
return reverseStringRec(str.slice(1)) + str[0];
}
再帰の場合、スタックには以下のように積まれます。文字列の最後尾まで行くのに注目してください。スタックから戻る時に、str[0]で最初の文字だけ連結していきます。
この再帰の解法では、与えられた文字列を最初の文字以外と最初の文字に分けて考えます。再帰的に最初の文字以外の部分に対して同じ操作を行い、最後に最初の文字を連結することで、文字列を逆順にします。
さらに、実践的な解法として、JavaScriptの組み込み関数を使った方法も紹介します。以下のコードをご覧ください。
実践版
function reverseString(str) {
return str
.split("")
.reverse()
.join("");
}
仕事だと、これが求められるかもしれません。誰が見てもわかりやすいですね。
Python版コード
# 単純な解法
def reverse_string(s):
return s[::-1]
# 再帰版
def reverse_string_rec(s):
if len(s) <= 1:
return s
return reverse_string_rec(s[1:]) + s[0]
# 実践版
def reverse_string_practical(s):
return ''.join(reversed(s))
# 使用例
input_string = "hello"
reversed_string = reverse_string(input_string)
print(reversed_string) # 出力: olleh
reversed_string_rec = reverse_string_rec(input_string)
print(reversed_string_rec) # 出力: olleh
reversed_string_practical = reverse_string_practical(input_string)
print(reversed_string_practical) # 出力: olleh
上記のコードでは、単純な解法では文字列をスライスを使って逆順にし、再帰版では再帰関数を用いて文字列を逆順にします。また、実践版では組み込み関数のreversed()を使って逆順にし、join()で結合します。
それぞれの関数を適用して、与えられた文字列を逆順にすることができます。上記の例では、入力文字列が"hello"である場合、それぞれの関数で逆順に変換した結果が表示されます。
この本は夢中になって読めると思います。なんせ、世の中を支えているアルゴリズムが出てくるのですから。公開鍵暗号方式の章は必読。
この記事が気に入ったらサポートをしてみませんか?