Letter Combinations of a Phone Number
class Solution {
List<String> result = new ArrayList<String>();
Map<Character, String> m = new HashMap<Character, String>();
public List<String> letterCombinations(String digits) {
if (digits.length() == 0) {
return result;
}
m.put('2', "abc");
m.put('3', "def");
m.put('4', "ghi");
m.put('5', "jkl");
m.put('6', "mno");
m.put('7', "pqrs");
m.put('8', "tuv");
m.put('9', "wxyz");
helper("", digits);
return result;
}
private void helper(String build, String digits) {
if (build.length() == digits.length()) {
result.add(build);
} else {
String perm = m.get(digits.charAt(build.length()));
for (int i = 0; i < perm.length(); i++) {
helper(build + perm.charAt(i), digits);
}
}
}
}Generate Parentheses
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<String>();
helper(result, 0, 0, n, "");
return result;
}
private void helper(List<String> result, int o, int c, int n, String build) {
if (build.length() == n * 2) {
result.add(build);
return;
} else {
if (o < n) {
helper(result, o + 1, c, n, build + "(");
}
if (o > c) {
helper(result, o, c + 1, n, build + ")");
}
}
}
}Permutations
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
result = []
self.helper(result, nums, 0, len(nums) - 1)
return result
def helper(self, result:List[List[int]], nums:List[int], s:int, e:int):
if (s == e):
result.append(nums)
else:
for i in range(s, e + 1):
nums[s], nums[e] = nums[e], nums[s]
self.helper(result, nums, s + 1, e)
nums[s], nums[e] = nums[e], nums[s]Wrong Answer
class Solution:
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
def backtrack(first = 0):
# if all integers are used up
if first == n:
output.append(nums[:])
for i in range(first, n):
# place i-th integer first
# in the current permutation
nums[first], nums[i] = nums[i], nums[first]
# use next integers to complete the permutations
backtrack(first + 1)
# backtrack
nums[first], nums[i] = nums[i], nums[first]
n = len(nums)
output = []
backtrack()
return output루션이
Subsets
class Solution {
List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<List<Integer>> subsets(int[] nums) {
List<Integer> cur = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
helper(nums, cur, i, 0);
}
return result;
}
private void helper(int[] nums, List<Integer> cur, int size, int loc) {
if (cur.size() == size) {
result.add(cur);
} else {
for (int j = loc; j < nums.length; j++) {
cur.add(nums[j]);
helper(nums, cur, size, loc + 1);
cur.remove(nums[j]);
}
}
}
}Runtime Error
class Solution {
List<List<Integer>> output = new ArrayList();
int n, k;
public void backtrack(int first, ArrayList<Integer> curr, int[] nums) {
// if the combination is done
if (curr.size() == k) {
output.add(new ArrayList(curr));
return;
}
for (int i = first; i < n; ++i) {
// add i into the current combination
curr.add(nums[i]);
// use next integers to complete the combination
backtrack(i + 1, curr, nums);
// backtrack
curr.remove(curr.size() - 1);
}
}
public List<List<Integer>> subsets(int[] nums) {
n = nums.length;
for (k = 0; k < n + 1; ++k) {
backtrack(0, new ArrayList<Integer>(), nums);
}
return output;
}
}루션이와 아예 같은데 왜 안되는지 모를???
Word Search
class Solution {
private char[][] board;
private int ROW;
private int COL;
public boolean exist(char[][] board, String word) {
this.board = board;
this.ROW = board.length;
this.COL = board[0].length;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (helper(word, 0, i, j)) {
return true;
}
}
}
return false;
}
private boolean helper(String word, int loc, int r, int c) {
if (loc > word.length()) {
return true;
}
if (r < 0 || r == this.ROW || c < 0 || c == this.COL
|| this.board[r][c] != word.charAt(loc)) return false;
boolean res = false;
this.board[r][c] = '#';
int[] posr = {0, 1, 0, -1};
int[] posc = {1, 0, -1, 0};
for (int i = 0; i < 4; i++) {
res = this.helper(word, loc + 1, r + posr[i], c + posc[i]);
if (res) break;
}
this.board[r][c] = word.charAt(loc);
return res;
}
}Runtime
왤케 많이나..
class Solution {
private char[][] board;
private int ROWS;
private int COLS;
public boolean exist(char[][] board, String word) {
this.board = board;
this.ROWS = board.length;
this.COLS = board[0].length;
for (int row = 0; row < this.ROWS; row++)
for (int col = 0; col < this.COLS; col++)
if (this.backtrack(row, col, word, 0))
return true;
return false;
}
protected boolean backtrack(int row, int col, String word, int index) {
if (index >= word.length())
return true;
if (row < 0 || row == this.ROWS || col < 0 || col == this.COLS
|| this.board[row][col] != word.charAt(index))
return false;
boolean ret = false;
this.board[row][col] = '#';
int[] rowOffsets = {0, 1, 0, -1};
int[] colOffsets = {1, 0, -1, 0};
for (int d = 0; d < 4; d++) {
ret = this.backtrack(row + rowOffsets[d], col + colOffsets[d], word, index + 1);
if (ret)
break;
}
this.board[row][col] = word.charAt(index);
return ret;
}
}
y