Graph Depth First Search

1. Split String

Give a string, you can choose to split the string after one character or two adjacent characters, and make the string to be composed of only one character or two characters. Output all possible results.

Input: "123"
Output: [["1","2","3"],["12","3"],["1","23"]]
Input: "12345"
Output: [["1","23","45"],["12","3","45"],["12","34","5"],["1","2","3","45"],["1","2","34","5"],["1","23","4","5"],["12","3","4","5"],["1","2","3","4","5"]]
def splitString(self, s):
res = []
self.backtrack(s, 0, [], res)
return res

def backtrack(self, s, i, ans, res):
if i == len(s):
res.append(ans[:])
return

for j in range(1, 3):
if i + j <= len(s):
num = s[i:i+j]
ans.append(num)
self.backtrack(s, i + j, ans, res)
ans.pop()

2. Letter Combinations of a Phone Number

Given a digit string excluded '0' and '1', return all possible letter combinations that the number could represent.

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Explanation:
'2' could be 'a', 'b' or 'c'
'3' could be 'd', 'e' or 'f'
Input: "5"
Output: ["j", "k", "l"]
class Solution:    KEYBOARD = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz',
}
def letterCombinations(self, digits):
result = []
if not digits:
return result
self.dfs(digits, 0, [], result)
return result

def dfs(self, digits, i, ans, result):
if i == len(digits):
result.append(''.join(ans))
return

for letter in Solution.KEYBOARD[digits[i]]:
ans.append(letter)
self.dfs(digits, i + 1, ans, result)
ans.pop()

3. Combination Sum II

Given an array num and a number target. Find all unique combinations in num where the numbers sum to target.

  • Each number in num can only be used once in one combination.
  • All numbers (including target) will be positive integers.
  • Numbers in a combination a1, a2, … , ak must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak)
  • Different combinations can be in any order.
  • The solution set must not contain duplicate combinations.
Input: num = [7,1,2,5,1,6,10], target = 8
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
Input: num = [1,1,1], target = 2
Output: [[1,1]]
Explanation: The solution set must not contain duplicate combinations.
class Solution:

def combinationSum2(self, num, target):
num = sorted(num)
results, ans, visited = [], [], [False] * len(num)
self.dfs(num, target, 0, 0, visited, ans, results)
return results
def dfs(self, num, target, start, now, visited, ans, results):
if now == target:
return results.append(ans[:])

for i in range(start, len(num)):
if now + num[i] <= target and (i == 0 or num[i] != num[i-1] or visited[i- 1] == True):
ans.append(num[i])
visited[i] = True
self.dfs(num, target, i+1, now + num[i], visited, ans, results)
ans.pop()
visited[i] = 0

4. Combination Sum

Given a set of candidtate numbers candidates and a target number target. Find all unique combinations in candidates where the numbers sums to target.

  • All numbers (including target) will be positive integers.
  • Numbers in a combination a1, a2, … , ak must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak)
  • Different combinations can be in any order.
  • The solution set must not contain duplicate combinations.
Input: candidates = [2, 3, 6, 7], target = 7
Output: [[7], [2, 2, 3]]
Input: candidates = [1], target = 3
Output: [[1, 1, 1]]
def combinationSum(self, candidates, target):
candidates = sorted(list(set(candidates)))
result = []
self.dfs(candidates, target, 0, [], result)
return result

def dfs(self, candidates, target, start, ans, result):
if target < 0:
return
if target == 0:
return result.append(ans[:])


for i in range(start, len(candidates)):
ans.append(candidates[i])
self.dfs(candidates, target - candidates[i], i, ans, result)
ans.pop()

5. N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other(Any two queens can't be in the same row, column, diagonal line).

Input:1
Output:
[["Q"]]
Input:4
Output:
[
// Solution 1
[".Q..",
"...Q",
"Q...",
"..Q."
],
// Solution 2
["..Q.",
"Q...",
"...Q",
".Q.."
]
]
class Solution:
def solveNQueens(self, n):
boards = []
visited = {
'col': set(),
'sum': set(),
'diff': set(),
}
self.dfs(n, [], visited, boards)
return boards

def dfs(self, n, permutation, visited, boards):
if n == len(permutation):
boards.append(self.draw(permutation))
return

row = len(permutation)
for col in range(n):
if not self.is_valid(permutation, visited, col):
continue
permutation.append(col)
visited['col'].add(col)
visited['sum'].add(row + col)
visited['diff'].add(row - col)
self.dfs(n, permutation, visited, boards)
visited['col'].remove(col)
visited['sum'].remove(row + col)
visited['diff'].remove(row - col)
permutation.pop()
# O(1)
def is_valid(self, permutation, visited, col):
row = len(permutation)
if col in visited['col']:
return False
if row + col in visited['sum']:
return False
if row - col in visited['diff']:
return False
return True

def draw(self, permutation):
board = []
n = len(permutation)
for col in permutation:
row_string = ''.join(['Q' if c == col else '.' for c in range(n)])
board.append(row_string)
return board
  • Each element in a subset must be in non-descending order.
  • The ordering between two subsets is free.
  • The solution set must not contain duplicate subsets.
Input: [0]
Output:
[
[],
[0]
]
Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
class Solution:

def subsetsWithDup(self, nums):
if not len(nums):
return [[]]

nums.sort()

res = []
self.dfs(nums, 0, None, [], res)
return res

def dfs(self, nums, i, prev, ans, res):
#print('i', i, 'prev', prev, 'ans', ans)
if i == len(nums):
res.append(ans[:])
return

if i - 1 >= 0 and nums[i] == nums[i-1]:
if prev == i - 1:
ans.append(nums[i])
self.dfs(nums, i + 1, i, ans, res)
ans.pop()
else:
ans.append(nums[i])
self.dfs(nums, i + 1, i, ans, res)
ans.pop()

self.dfs(nums, i + 1, prev, ans, res)

7. Subsets

Given a set of distinct integers, return all possible subsets.

  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.
Input: [0]
Output:
[
[],
[0]
]
Input: [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
class Solution:

def subsets(self, nums):
nums = sorted(nums)
results = []
self.dfs(nums, 0, [], results)
return results

def dfs(self, nums, start, subset, results):
results.append(subset[:])
for i in range(start, len(nums)):
subset.append(nums[i])
self.dfs(nums, i + 1, subset, results)
subset.pop()

8. Permutations

Given a list of numbers, return all possible permutations.

Example

Example 1:

Input: [1]
Output:
[
[1]
]
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
class Solution:

def permute(self, nums):
visited = [False] * len(nums)

results = []
self.permutations(nums, visited, [], results)
return results

def permutations(self, nums, visited, ans, results):
lenth = len(nums)
if len(ans) == len(nums):
return results.append(ans[:])

for i in range(0, lenth):
if visited[i]:
continue
ans.append(nums[i])
visited[i] = True
self.permutations(nums, visited, ans, results)
visited[i] = False
ans.pop()

9. Word Pattern II

Given a pattern and a string str, find if str follows the same pattern.

Input:
pattern = "abab"
str = "redblueredblue"
Output: true
Explanation: "a"->"red","b"->"blue"
Input:
pattern = "aaaa"
str = "asdasdasdasd"
Output: true
Explanation: "a"->"asd"
Input:
pattern = "aabb"
str = "xyzabcxzyabc"
Output: false
class Solution:
def wordPatternMatch(self, pattern, str):
return self.is_match(pattern, str, {}, set())
def is_match(self, pattern, string, mapping, used):
if not pattern:
return not string

char = pattern[0]
if char in mapping:
word = mapping[char]
if not string.startswith(word):
return False
return self.is_match(pattern[1:], string[len(word):], mapping, used)

for i in range(len(string)):
word = string[:i + 1]
if word in used:
continue

used.add(word)
mapping[char] = word

if self.is_match(pattern[1:], string[i + 1:], mapping, used):
return True

del mapping[char]
used.remove(word)

return False

10. Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, output sequence in dictionary order.
Transformation rule such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • At least one solution exists.
Input:start = "a",end = "c",dict =["a","b","c"]
Output:[["a","c"]]
Explanation:
"a"->"c"
Input:start ="hit",end = "cog",dict =["hot","dot","dog","lot","log"]
Output:[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation:
1."hit"->"hot"->"dot"->"dog"->"cog"
2."hit"->"hot"->"lot"->"log"->"cog"
The dictionary order of the first sequence is less than that of the second.
from collections import deque
class Solution:

def findLadders(self, start, end, dict):
dict.add(start)
dict.add(end)
distance = {}

self.bfs(end, distance, dict)

results = []
self.dfs(start, end, distance, dict, [start], results)

return results
def bfs(self, start, distance, dict):
distance[start] = 0
queue = deque([start])
while queue:
word = queue.popleft()
for next_word in self.get_next_words(word, dict):
if next_word not in distance:
distance[next_word] = distance[word] + 1
queue.append(next_word)

def get_next_words(self, word, dict):
words = []
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = word[:i] + c + word[i + 1:]
if next_word != word and next_word in dict:
words.append(next_word)
return words

def dfs(self, curt, target, distance, dict, path, results):
if curt == target:
results.append(list(path))
return

for word in self.get_next_words(curt, dict):
if distance[word] != distance[curt] - 1:
continue
path.append(word)
self.dfs(word, target, distance, dict, path, results)
path.pop()

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store