backtracking

exist.py

def exist(board, word):
    '''
    Leetcode 79. Word Search
    Backtracking을 활용
    '''
    rows, cols = len(board), len(board[0])
    visit = set()

    def dfs(r, c, i):

        if i == len(word):
            return True
        if (r not in range(rows) or c not in range(cols) 
        or board[r][c] != word[i] or (r, c) in visit):
            return False
        visit.add((r, c))
        res = (dfs(r+1, c, i+1) or dfs(r-1, c, i+1) or dfs(r, c+1, i+1) or dfs(r, c-1, i+1))
        return res

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

b = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
w = "ABCCED"
exist(b, w)

letterCombinations.py

def letterCombinations(digits):
    '''
    Leetcode 17. Letter Combinations of a Phone Number
    '''
    res = []
    digitChar = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "qprs",
        "8": "tuv",
        "9": "wxyz"
    }
    
    def backtrack(i, curStr):
        if len(curStr) == len(digits):
            res.append(curStr)
            return
        for c in digitChar[digits[i]]:
            backtrack(i+1, curStr + c)
    if digits:
        backtrack(0, "")
        
    return res
print(letterCombinations("23"))

N_M.py

'''
백준 15649. 1 ~ N으로 M개짜리 조합 만들기
'''
n,m = list(map(int,input().split()))
 
s = []
 
def dfs():
    if len(s)==m:
        print(' '.join(map(str,s)))
        return
    
    for i in range(1,n+1):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()
 
dfs()

'''
백준 15650. 1 ~ N으로 M개짜리 수열 만들기
'''
n,m = list(map(int,input().split()))
 
s = []
 
def dfs(start):
    if len(s)==m:
        if s == sorted(s):
            print(' '.join(map(str,s)))
        return
    
    for i in range(1,n+1):
        if i not in s:
            s.append(i)
            dfs(i+1)
            s.pop()
 
dfs(1)

palindrome.py

def isPali(s):
    l = 0
    h = len(s) - 1
    while l < h:
        if s[l] != s[h]:
            return False
        l, h = l+1, h-1
    return True

'''
Leetcode 131. Palindrome Partitioning
'''
def partition(s):
    res = []
    part = []
    
    def dfs(i):
        if i >= len(s):
            res.append(part.copy())
            return
        for j in range(i, len(s)):
            if isPali(s, i, j):
                part.append(s[i:j+1])
                dfs(j+1)
                part.pop()
    dfs(0)
    return res

def isPali(s, l, r):
    while l < r:
        if s[l] != s[r]:
            return False
        l, r = l + 1, r - 1
    return True

print(partition('aab'))