指定したオブジェクトではなくDFSパラメータを指定する必要がある場合は[leet 22]

1962 ワード
python DFS Parentheses コーディングテスト テキストリンク
leetcode 22 Generate Parentheses

固定DFSの変数


私は通常DFSを回すときに以下の方法を使用します.
1.チェックする変数にルートをマップする
2.根元から次の到達可能な位置を選択(togo)
3.対togo:dfs for loc in togoを実行する:
def helper(path, root, cum):
    nonlocal ans, n
    if len(path)==n:
        ans.append(path)
        return
    path.append(root)
    cum += root
    if cum == 0: togo = [1]
    if cum == n: togo = [-1]
    else: togo[-1, 1]
    for loc in togo:
        dfs_helper(path, loc, cum)
しかし、これで初めてリフに行って、2番目のリフを探したとき、pathはもういっぱいになりました.ただし、戻る前にpathを初期化すると、次のreproveのナビゲーションもpath=Noneの状態で再開されないため、これは不可能である.
この問題では,これを防止するために変数に割り当てず,再帰関数に直接値を付与する.リフに一度行っても、定価で出発するので、希望の探索ができます.
if cum == 0:
            dfs_helper(str1+'(', cum+1)
        elif cum == n:
            dfs_helper(str1+')', cum-1)
        else:
            dfs_helper(str1+'(', cum+1)
            dfs_helper(str1+')', cum-1)

Question


nを使用してカッコに有効なすべてのカッコ文字を作成

Solution


PSEUDO 1
  • 前後にそれぞれ()を入れ、中間2 n-2個の位置からn-1個の組み合わせを抽出し、「(」が入るindex
  • pool(すべて可能なサンプル)
  • poolの全ての場合、isValid
    • ソリューション1も時間制限で通過しますが、位置決め長が長いため、プールコードは次のgithubを参照してください.
    PSEUDO 2
  • DFSは、pathまたはcumに値を指定するとループで変更が続くので、直接関数を挿入する形で
    path+=')',cum-=1のようです.
    • def sol_2(n):
    ans = list()
    def dfs_helper(str1, cum):
        nonlocal ans, n
        if len(str1) == n*2:
            if cum == 0:
                ans.append(str1)
            return
        
        if cum == 0:
            dfs_helper(str1+'(', cum+1)
        elif cum == n:
            dfs_helper(str1+')', cum-1)
        else:
            dfs_helper(str1+'(', cum+1)
            dfs_helper(str1+')', cum-1)
    dfs_helper(str(), 0)
    return ans
    2021. 03. 10
    Lifecycle&条件レンダリング