22. Generate Parentheses
public class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
if (n == 0) return result;
dfs(result, new StringBuilder(), n, n);
return result;
}
private void dfs(List<String> result, StringBuilder sb, int left, int right) {
if (left == 0 && right == 0) result.add(sb.toString());
int length = sb.length();
if (left > 0) {
sb.append('(');
dfs(result, sb, left - 1, right);
sb.setLength(length);
}
if (right > left) {
sb.append(')');
dfs(result, sb, left, right - 1);
sb.setLength(length);
}
}
}
93. Restore IP Addresses
依旧是 DFS + Backtracking
每一步有三种可能：选一位数，两位数，还有三位数。
用一个ipIndex来记录我们解析了几个字节，一共是4个。
只有前面的字节valid我们才能继续，所以Backtracking操作都在if语句中完成。
一个需要注意的边界条件是当选取多位数时，第一位不能是0，因为 '020' 或 '05' 都不是有效的 IP 地址。
当 DFS 的可能性比较多，而且只在 index 上有区别的时候，用 for 循环就好了。
public class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<>();
if (s == null || s.length() == 0 || s.length() > 12) return result;
dfs(result, new StringBuilder(), s, 0, 0);
return result;
}
private void dfs(List<String> result, StringBuilder sb, String s, int ipIndex, int strIndex) {
if (ipIndex == 4 && strIndex == s.length()) {
sb.setLength(sb.length() - 1);
result.add(sb.toString());
return;
}
int length = sb.length();
for (int i = 0; i < 3; ++i) {
if (strIndex + i < s.length()) {
String str = s.substring(strIndex, strIndex + i + 1);
if (isValid(str, i)) {
sb.append(str);
sb.append(".");
dfs(result, sb, s, ipIndex + 1, strIndex + i + 1);
sb.setLength(length);
}
}
}
}
private boolean isValid(String str, int i) {
if (i == 0) return true;
if (i > 0 && str.charAt(0) == '0') return false;
int number = 0;
for (int j = 0; j < str.length(); ++j) {
number = number * 10 + str.charAt(j) - '0';
}
if (number > 255 || number < 0) return false;
return true;
}
}
17. Letter Combinations of a Phone Number
DFS 写法就是做了无数次的 backtracking 写法。本质上，都是殊途同归的状态空间搜索罢了。
public class Solution {
public ArrayList<String> letterCombinations(String digits) {
// Write your code here
ArrayList<String> result = new ArrayList<>();
if (digits == null || digits.length() == 0) return result;
String[] map = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
dfs(result, new StringBuilder(), digits, 0, map);
return result;
}
private void dfs(List<String> result, StringBuilder sb, String digits,
int index, String[] map) {
if (sb.length() == digits.length()) {
result.add(sb.toString());
return;
}
for (int i = index; i < digits.length(); ++i) {
String str = map[digits.charAt(i) - '0'];
for (int j = 0; j < str.length(); ++j) {
int length = sb.length();
sb.append(str.charAt(j));
dfs(result, sb, digits, i + 1, map);
sb.setLength(length);
}
}
}
}
131. Palindrome Partitioning
一个比较简单暴力的搜索办法就是直接 DFS + Backtracking，每一步上需要考虑的字问题数量和当前字符串剩余长度相等。
这个解法速度是很慢的。
public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
if (s == null || s.length() == 0) return result;
List<String> list = new ArrayList<>();
dfs(result, list, 0, s);
return result;
}
private void dfs(List<List<String>> result, List<String> list,
int index, String s) {
if (index == s.length()) {
result.add(new ArrayList<String>(list));
return;
}
for (int i = index; i < s.length(); ++i) {
String str = s.substring(index, i + 1);
if(!isValid(str)) continue;
list.add(str);
dfs(result, list, i + 1, s);
list.remove(list.size() - 1);
}
}
private boolean isValid(String s) {
for (int i = 0; i < s.length(); ++i) {
int j = s.length() - i - 1;
if (s.charAt(i) != s.charAt(j)) return false;
j++;
}
return true;
}
}
267. Palindrome Permutation II
267紧接266，返回所有的可能palindrome，属于搜索问题。根据 palindrome 结构做 DFS + backtracking
仿照permutation那道题的思路写，解法是对的，就是这个暴力解太慢了。挂在了“aaaaaaaa...”那个testcase上。
public class Solution {
public List<String> generatePalindromes(String s) {
List<String> result = new ArrayList<>();
if (s == null || s.length() == 0) return result;
char[] array = s.toCharArray();
Arrays.sort(array);
int[] visited = new int[s.length()];
dfs(result, new StringBuilder(), visited, array);
return result;
}
private void dfs(List<String> result, StringBuilder sb,
int[] visited, char[] array) {
if (sb.length() == array.length && isValid(sb.toString())) result.add(sb.toString());
int length = sb.length();
for (int i = 0; i < array.length; ++i) {
if (visited[i] == 1 || i != 0 && array[i] == array[i - 1] && visited[i - 1] == 0) continue;
sb.append(array[i]);
visited[i] = 1;
dfs(result, sb, visited, array);
visited[i] = 0;
sb.setLength(length);
}
}
private boolean isValid(String s) {
for (int i = 0; i < s.length(); ++i) {
int j = s.length() - i - 1;
if (s.charAt(i) != s.charAt(j)) return false;
j++;
}
return true;
}
}
401. Binary Watch
题目给的是亮灯的数量，所以要考虑hour亮几个，minute亮几个。设好hour数组和minute数组，分别枚举就行了。最后注意格式的处理。
public class Solution {
public List<String> readBinaryWatch(int num) {
List<String> res=new ArrayList<String>();
int[] h=new int[]{8,4,2,1}, m=new int[]{32,16,8,4,2,1};
for(int i=0;i<=num;i++){
List<Integer> listH=helper(h, i);
List<Integer> listM=helper(m, num-i);
for(int hh:listH){
if(hh>=12)
continue;
for(int mm:listM){
if(mm>=60)
continue;
res.add(hh+":"+ (mm<10? "0"+mm:mm));
}
}
}
return res;
}
public List<Integer> helper(int[] s, int i){
List<Integer> res=new ArrayList<Integer>();
helper1(s, i, 0, 0, res);
return res;
}
public void helper1(int[] s, int count, int i, int sum, List<Integer> res){
if(count==0){
res.add(sum);
return;
}
for(int j=i;j<s.length;j++)
helper1(s, count-1, j+1, sum+s[j], res);
}
}
526. Beautiful Arrangement
DFS分别找出每一个可能的数，并且用一个数组来保存visited状态。
public class Solution {
int count=0;
public int countArrangement(int N) {
if(N==0)
return 0;
dfs(N, new int[N+1], 1);
return count;
}
public void dfs(int N, int[] sub, int indi){
if(indi>N){
count++;
return;
}
for(int i=1;i<=N;i++){
if(sub[i]==0&&(i%indi==0||indi%i==0)){
sub[i]=1;
dfs(N, sub, indi+1);
sub[i]=0;
}
}
}
}