【leetcode × Python】任意の英数字から隣り合う2つの文字が同じ型でないことを確認する

はじめに

以前にも、leetcodeは使用したことがあったのですが、今回、2年ぶりぐらいに解いてみました。
その時はEasyモードですら難しく何時間もかけて解いていました。
当時は、Hintと回答を見ながらやっと解ける感じでした。

そこで今回、久しぶりにEasyモードを解いてみることにしました。

目次

1.実際に解いた問題
2.私が出した回答がこちら
3.リファクタリングしていく
4.リファクタリング後のコード
5.最後に

1. 実際に解いた問題

leetcodeではランダムに問題が選択できるのですが、そこからEasyを選びました
今回解いた問題がこちらです。

以下が問題を日本語訳したものです

英数字の文字列sが与えられる（英数字の文字列とは、小文字の英字と数字からなる文字列である）。

あなたは，どの文字も他の文字に続かず，どの数字も他の数字に続かないような文字列の順列を見つけなければならない．つまり、隣り合う2つの文字が同じ型であることはない。

再フォーマットされた文字列を返すか、文字列を再フォーマットできない場合は空文字列を返す。

例1．
入力: s = "a0b1c2"
出力: "0a1b2c"
説明 0a1b2c" の場合、隣接する2つの文字が同じ型であることはない。"a0b1c2", "0a1b2c", "0c2a1b "も有効な並べ方である。

例2:
入力: s = "leetcode"
出力は ""
説明 "leetcode"は文字だけなので、数字で区切ることができない。

例3:
入力: s = "1229857369"
出力: ""
説明の通りです。"1229857369 "は数字だけなので、文字で区切ることができない。
 
制約事項
1 <= s.length <= 500
sは小文字の英字と数字のどちらか一方のみからなる。

2. 私が出した回答がこちら

私の場合は、Pythonを使用して書いています
今回は、leetcode上で見れる解答やHintは見ずに解いていきました

leetcode.py

class Solution:
    def reformat(self, s: str) -> str:
        # リストに
        word_list = list(s)

        # 数字だけのリスト
        num_list = [w for w in word_list if w.isdigit()]

        # 英字のリスト
        non_num_list = list(filter(lambda x: x not in num_list, word_list))

        len_num_list = len(num_list)
        len_non_num_list = len(non_num_list)
        # 配列数チェック
        if len_num_list <= len_non_num_list + 1 and len_num_list >= len_non_num_list - 1:
            if len_num_list >= len_non_num_list:
                return Solution._filter_str(num_list, non_num_list)
            else:
                return Solution._filter_str(non_num_list, num_list)
        else:
            return ""

    def _filter_str(inserted: list, inserting: list):
        for i, insert in enumerate(inserting):
            odd = (i*2+2)-1
            inserted.insert(odd, insert)
        return "".join(inserted)

まずは、与えられた文字列を数字だけのリスト、英字のリストに分けました

そして、リスト同士の長さが±1の範囲の時には、フィルターをかけた文字列。
そうでない場合は、から文字を返すようにしています

_filter_strでフィルターをかけている箇所では、
リストの長さが長い方に対して、短い方のリストをループ内で挿入しています。

ループ内では、奇数位置へ一方のリストから取り出したものを挿入していくことで、隣り合う2つの文字が同じ型にならないようにしています。

最後に、出来上がったリストから文字列へ変換しています

そして、

leetcodeでは、他の人の解答も見れるのがやはり魅力的ですね。
解答後に、他の人の解答も確認してみると直せそうな箇所がワンサカ出てきたのでリファクタしていきました

3. リファクタリングしていく

命名の修正

num_listと、non_num_listがなんかビミョーやなーと思っていました。

修正前.py

num_list
non_num_list

修正後.py

digits
letters

num_list → digits
non_num_list → letters

このほうが良さそう

isdigit()：リストにする必要なかった

変更前.py

# リストに
word_list = list(s)

# 数字だけのリスト
digits = [w for w in word_list if w.isdigit()]

isdigit はstrに対して使用するものなのでlistに変換する必要はなかったです

変更後.py

digits = [w for w in s if w.isdigit()]

数字以外のリスト ってのがそもそもおかしい

修正前.py

letters = list(filter(lambda x: x not in num_list, word_list))

ここでは本来、英字のリストが入る部分です。
命名は先ほど修正しましたが、filter内でlambda式を使用している部分。
filterでnum_listに含まれないものを抽出してと一目で分かるものではありませんでした。

シンプルに英字を抽出すれば良いだけなのでisalphaを使用すれば簡単にとれました
また、word_list = list(s)でリストにする必要も無くなっているので修正すると

修正後.py

letters = [w for w in s if w.isalpha()]

ifのネストどうにかしよう

修正前.py

if len_num_list <= len_non_num_list + 1 and len_num_list >= len_non_num_list - 1:
    if len_num_list >= len_non_num_list:
        return Solution._filter_str(num_list, non_num_list)
    else:
        return Solution._filter_str(non_num_list, num_list)
else:
    return ""

早期リターンさせておきます

修正後.py

if len_digits > len_non_digits + 1 and len_digits < len_non_digits - 1:
    return ""

if len_digits >= len_non_digits:
    return Solution._filter_str(digits, non_digits)
else:
    return Solution._filter_str(non_digits, digits)

リスト同士の長さが±1の範囲の時 の 条件を修正

syuuseimae.py

if len_num_list <= len_non_num_list + 1 and len_num_list >= len_non_num_list - 1:

「なんか、可読性低いかなぁ」 と思っていたところか解答の中から分かりやすいものがありました

修正後.py

if abs(len_digits - len_non_digits) > 1:

うん、この方がずっといい。

abs はビルトイン関数ですが、絶対値を返してくれます。
そのため、修正前の条件と同じになりますね。
（absを使う発想がなかった...）

ループ内では、奇数位置へ挿入する部分

ここも複雑になり過ぎていたので、解答参考に修正しました

修正前.py

    if len(digits) >= len(letters):
        return Solution._filter_str(digits, letters)
    else:
        return Solution._filter_str(letters, digits)

def _filter_str(inserted: list, inserting: list):
    for i, insert in enumerate(inserting):
        odd = (i*2+2)-1
        inserted.insert(odd, insert)
    return "".join(inserted)

修正後.py

filtered = []
flag = len(letters) > len(digits)
while letters or digits:
    filtered.append(letters.pop() if flag else digits.pop())
    flag = not flag
return "".join(filtered)

英字の方が長いかどうかを示すフラグ（flag）を用意しています。
while letters or digits:でどちらか一方のリストの中身が存在する限りループを回しています
whileループの1度目では、長い方リストを新たなリストfilteredへ詰めていっています。
そして、ループ内で最後にフラグを反転させることで交互にリストの中身をpopで削除して取り出し、filteredに詰めたものを文字列にして完成です。

4. リファクタリング後のコード

修正前のコードはこちら

修正前.py

class Solution:
    def reformat(self, s: str) -> str:
        # リストに
        word_list = list(s)

        # 数字だけのリスト
        num_list = [w for w in word_list if w.isdigit()]

        # 英字のリスト
        non_num_list = list(filter(lambda x: x not in num_list, word_list))

        len_num_list = len(num_list)
        len_non_num_list = len(non_num_list)
        # 配列数チェック
        if len_num_list <= len_non_num_list + 1 and len_num_list >= len_non_num_list - 1:
            if len_num_list >= len_non_num_list:
                return Solution._filter_str(num_list, non_num_list)
            else:
                return Solution._filter_str(non_num_list, num_list)
        else:
            return ""

    def _filter_str(inserted: list, inserting: list):
        for i, insert in enumerate(inserting):
            odd = (i*2+2)-1
            inserted.insert(odd, insert)
        return "".join(inserted)

修正後.py

class Solution:
    def reformat(self, s: str) -> str:
        # 数字だけのリスト
        digits = [w for w in s if w.isdigit()]

        # 英字のリスト
        letters = [w for w in s if w.isalpha()]

        if abs(len(digits) - len(letters)) > 1:
            return ""

        filtered = []
        flag = len(letters) > len(digits)
        while letters or digits:
            filtered.append(letters.pop() if flag else digits.pop())
            flag = not flag
        return "".join(filtered)

こうみると最初のコードはかなり酷い。。
だいぶ、スッキリしました

5. 最後に

やはり、Easyモードでも難しいです。
解答を見ずに自分で解答を導けたことに関しては、良かったと思います

ただ、解き終えるまでにかなりの時間を要しました。
繰り返し、問題解く → 他の回答でリファクタ。

これで割と、コツが掴めそうな感覚がありました。

また、leetcodeやろう😌