D - String Equivalence

パナソニックプログラミングコンテストのD問題。

• https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_d

|s| = |t|である

この意味は、オートマトンの記号で、sとtが同じ長さの文字列であることを示す。

再帰の場合

def solve():  
    N = int(input())
    # ord("a") Unicode コードポイントを返す
    codepoint = ord("a")

    # w : 標準形文字列
    # i : 出力された標準形文字列の辞書順で最も遅い文字
    def dfs(w, i):
        # ベースケース
        if len(w) == N:
            print(w)
            return

        # 辞書順で以前に出力済の文字までを追加する
        for j in range(i):
            dfs(w+chr(j+codepoint), i)

        # 辞書順で以前に出力済の文字 + 1まで
        dfs(w + chr(i+codepoint), i + 1)

    dfs("", 0)


# Solve
if __name__ == "__main__":  
    solve()

回答としては通りとなる。

ord()はUnicode コードポイントを返す標準関数であり、文字列を辞書順で一文字ずつ先に進めるときに使える。
chr()は逆。

再帰を使わない場合

def solve():  
    N = int(input())
    # ord("a") Unicode コードポイントを返す
    codepoint = ord("a")

    i = 1
    ans = [["a", 1]]
    while i < N:
        tmp = []
        for w, j in ans:
            for k in range(j+1):
                if k != j:
                    tmp.append([w + chr(codepoint+k), j])
                else:
                    tmp.append([w + chr(codepoint+k), j+1])
        ans = tmp
        i += 1

    [print(a[0]) for a in ans]

    # Solve
if __name__ == "__main__":  
    solve()

こんな感じになる。 幅優先探索になっている。