Leetcode 78. Subsets.
Back-tracking原理
Subsets题，时间复杂度一般是O(2^n), 因为 2^n是子集的数量级。如果要得到子集的集合，就必须遍历子集 (找出每个子集并add到总集) ，所以有O(2^n)。
经典做法，写backTracking()方法，其中有for循环+recursive调用。
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums == null || nums.length == 0) return res;
backTracking(res,new ArrayList<>(),nums,0);
return res;
}
private void backTracking(List<List<Integer>> res, List<Integer> tempList, int[] nums, int level){
res.add( new ArrayList<>(tempList));
for(int i=level; i<nums.length; i++){ //从level开始，而不是从0开始
tempList.add(nums[i]);
backTracking(res,tempList,nums,i+1); //经过这一步之后，res增加了很多新元素，但tempList每次backTracking都先增加后减少元素，tempList经过这个步骤之后是维持原样的
tempList.remove(tempList.size()-1); // add和remove对应。
}
}
}
Leetcode 90. Subsets II. 【Medium】
只在 Leetcode 78的基础上加了一个判断句。
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums == null || nums.length == 0) return res;
Arrays.sort(nums);
helper(res, new ArrayList<>(), nums, 0);
return res;
}
private void helper(List<List<Integer>> res, List<Integer> tempList, int[] nums, int start){
res.add(new ArrayList<>(tempList));
for(int i=start; i<nums.length; i++){
if(i != start && nums[i] == nums[i-1]) continue; // 必须是 i!=level. 而不是i!=0.
tempList.add(nums[i]);
helper(res, tempList, nums, i+1);
tempList.remove(tempList.size()-1);
}
//为什么单凭nums[i] == nums[i-1]不行，而是需要i!=level呢？这是因为nums[level]是必须选择的数。
// 例如[1,2,2,2,4,5],
//如果是 i != 0 && nums[i] == nums[i-1],就肯定缺了[1,2,2,4,5] 等。
//如果是 nums[i] == nums[i-1]，就肯定缺了 [1,2,2]和[1,2,2,2] 等。
// nums[level]是必须加入的数。例如它的本身也是其subset,[1,2,2,2,4,5], i!=level 保证了nums[i] == nums[i-1]不会忽略了全集
}
}
Leetcode 77. Combinations. 【Medium】
典型的 back-tracking 题目。设置了 tempList 和 level 来记录。
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
if(k==0) return res;
helper(res, new ArrayList<>(),n,k,1); //因为我们是直接从1～n选择，而不是从长为n的nums数组中选择
return res;
}
private void helper(List<List<Integer>> res, List<Integer> tempList, int n, int k, int level){
if(k == 0){ //说明tempList中已经收集了k个数。在for循环之前就判断。
res.add(new ArrayList<>(tempList));
return;
}
for(int i=level; i<=n; i++){ //从1到n
tempList.add(i);
helper(res, tempList,n,k-1,i+1); //因为加入了i，所以还需要k-1个数
tempList.remove(tempList.size()-1);
}
}
}
问题：what is the time complexity of generating all combinations for a given set?
https://stackoverflow.com/questions/31120402/complexity-when-generating-all-combinations/40944807
排列： Arrangement 或者 Permutation。
组合：Combination.
First, there is nothing wrong with using O(n! / (n-k)!k!) - or any other function f(n) as O(f(n)), but I believe you are looking for a simpler solution that still holds the same set.
If you are willing to look at the size of the subset k as constant,
for k<=n-k:
n! / ((n-k)!k!) = ((n-k+1) (n-k+2) (n-k+3) ... n ) / k!
But the above is actually (n^k + O(n^(k-1))) / k!, which is in O(n^k)
Similarly, if n-k<k, you get O(n^(n-k))
Which gives us 答案：O(n^min{k,n-k})
Leetcode 39. Combination Sum. 【Medium】
因为允许重复，所以recursive中helper是从自身 (i) 开始, 而不是从 i+1 开始。
Time: O(2^n), Space: O(n)
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
if(candidates == null || candidates.length == 0) return res;
helper(res, new ArrayList<>(), candidates, target, 0);
return res;
}
private void helper(List<List<Integer>> res, List<Integer> tempList, int[] candidates, int target, int start){
if(target < 0) return;
if(target == 0) res.add(new ArrayList<>(tempList));
for(int i = start; i<candidates.length; i++){
tempList.add(candidates[i]);
helper(res,tempList,candidates,target-candidates[i],i); //因为允许重复，所以从i开始。
tempList.remove(tempList.size()-1);
}
}
}
leetcode 216. Combination Sum III. 【】
用k-1和n-i,都用来更新k和n，但不会改变原来的k和n值(因为int是八大primitive types之一)
class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> res = new ArrayList<>();
helper(res,new ArrayList<>(),k,n,1); //不需要Arrays.sort().
//需要Arrays.sort()的情况：提供的int[]存在重复数字(且要求set中不能有相同的combinations【即set元素的唯一性】)。
return res;
}
private void helper(List<List<Integer>> res, List<Integer> tempList, int k, int n, int start){
if(n<0) return;
if(n==0 && k==0){ // n和k都在recursive过程中被缩减
res.add(new ArrayList<>(tempList));
return;
}
for(int i=start; i<10; i++){
tempList.add(i);
helper(res,tempList,k-1,n-i,i+1); //k-1和n-i,都用来更新k和n但不会改变原来的k和n值; i+1而不是start+1
tempList.remove(tempList.size()-1);
}
}
}
leetcode 377. Combination Sum IV. 【Medium】
题目对顺序有要求，不是组合(combination)而是排列(Permutation)。参考Leetcode 518才是permutation sum.
在permutation的情况下，用back-tracking的做法的话，(特点是不再需要int start参数)，做法超时，不能通过测试。
所以凡是permutation(排列)(要考虑顺序)，都优先考虑能不能用dp等方法做。若是最终的结果数量是2^n或n ! , 那才用back-tracking.
方法1，Dp方法
Time: O(k*n), Space:O(k)
//Dp 方法
public int combinationSum4(int[] nums, int target) {
int[] res = new int[target+1];
res[0] = 1;
for(int i=1; i<res.length; i++){
for(int num: nums){
if(i-num >=0){
res[i] += res[i-num];
}
}
}
return res[target];
}
方法2，【难解释+时间复杂度高，不建议】Time: O(2^n), Space:O(n)
iterative形式的back-tracking方法
没明白：为什么这种做法能够区分(1,2,1)和(1,1,2) ？
//设置一个HashMap 记录(target, 达到target的排列有几个)
public int combinationSum4(int[] nums, int target) {
if(nums.length ==0) return 0;
HashMap<Integer,Integer> map = new HashMap<>();
return helper(nums,target,map);
}
private int helper(int[] nums, int target, HashMap<Integer,Integer> map){
if(target<0) return 0;
if(target==0) return 1;
if(map.containsKey(target)) return map.get(target);
int res = 0;
for(int i=0; i<nums.length; i++){
res += helper(nums,target-nums[i],map);
}
map.put(target,res);
return res;
}
Leetcode 254. Factor Combinations. 【Medium】
看清题意，典型的组合题(combination)。难点在于helper前半部分有关结束helper的判断。
Time: O(nlogn), 有争议。
formula 1: time = (the number of nodes in the recursive tree) * (the time each node takes up)
formula 2: the number of nodes in the recursive tree =
(the most number of branches among each node) ^ (the height of the tree)
For the number of branches, it has at most N (from 2 to n) and in terms of the height of the tree, it should be logN since when the given number n is only decomposed by 2 will lead to the solution which has the longest length (pls take 32 as example in the description page). Thus, the number of nodes = (N)^(logN). And since each node only takes up O(1) time, therefore, the total time should be O(N^(logN))
class Solution {
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> res = new ArrayList<>();
helper(res,new ArrayList<>(),n,2);
return res;
}
private void helper(List<List<Integer>> res, List<Integer> tempList, int n, int start){
if(n==1){
if(tempList.size() >= 2){ // 1)防止空集 2) 防止n本身, 单个数
res.add(new ArrayList<>(tempList));
return;
}
}
for(int i=start; i<=n; i++){ //必须从start开始。若是从2开始，就是排列permutation了。
//而且要<= ,因为要把整除最后遍历的那个数加入，如21=3*7,若无=号，就只有[3]而不是[3,7]
if(n%i == 0){
tempList.add(i);
helper(res,tempList,n/i,i); //从i开始再次遍历。防止排列结果出现(permutation)
tempList.remove(tempList.size()-1);
}
}
}
}
- Permutations. 【Medium】
这题是permutation题。排列题，不传入start参数，从而考虑到顺序。
所以凡是permutation(排列)(要考虑顺序)，都优先考虑能不能用dp等方法做。若是最终的结果数量是2^n或n ! , 那才用back-tracking.
Space: res中有n!个list，每个list有n个数，所以是O(nn!).
Time: 方法1是O(nn!)，但可以改进为O(n!).
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums == null || nums.length == 0) return res;
helper(res, new ArrayList<>(), nums);
return res;
}
private void helper(List<List<Integer>> res, List<Integer> tempList, int[] nums){
if(tempList.size()==nums.length){
res.add(new ArrayList<>(tempList));
return;
}
for(int i=0; i<nums.length; i++){
if(tempList.contains(nums[i])) continue; //contains()需要遍历list，时间复杂度为O(n), 导致这个方法的Time: O(n*n!). 若要改进, 需要用HashSet或者boolean[ ]
tempList.add(nums[i]);
helper(res,tempList,nums);
tempList.remove(tempList.size()-1);
}
}
}
HashSet 介绍：
HashSet可以看成是HashMap的一种特殊结构,HashSet存储的元素是仅仅是HashMap的key，因此hashSet可以过滤重复的值，同时采用了Hash表结构HashSet是一种非线程安全的存储结构，在多线程下需要线程同步。
HashSet的add方法：hashSet实际上add元素时候是把将要存入的这个元素当做key值调用hashMap的put方法，放入hashMap中的，value放一个空的对象。因此hashSet,put元素的时间复杂度基本上是o(1),除了hash冲突。
HashSet的contains方法: hashSet的contains方法是调用map.containsKey(O)方法的，containsKey(o)是根据hash函数去做散列的，所以与元素的多少无关，无论是多少元素containsKey(o)的时间复杂度基本上O(1)。
用HashSet的O(1)的contains()方法, 消除原来的list.contains()导致的O(n)。
在原permute()方法中：
helper(res, new ArrayList<>(), nums, new HashSet<>());
private void helper(List<List<Integer>> res, List<Integer> tempList, int[] nums,Set<Integer> tempSet){
//传入Set<Integer> tempSet
if(tempList.size()==nums.length){
res.add(new ArrayList<>(tempList));
return;
}
for(int i=0; i<nums.length; i++){
if(tempSet.contains(nums[i])) continue;
tempList.add(nums[i]);
tempSet.add(nums[i]);
helper(res,tempList,nums,tempSet);
tempSet.remove(tempList.get(tempList.size()-1));
tempList.remove(tempList.size()-1);
}
}
用boolean array的O(1), 消除原来的list.contains()导致的O(n)。
在原permute()方法中：
boolean[] visited = new boolean[nums.length];
helper(res, new ArrayList<>(), nums, visited);
private void helper(List<List<Integer>> res, List<Integer> tempList, int[] nums, boolean[] visited){
if(tempList.size()==nums.length){
res.add(new ArrayList<>(tempList));
return;
}
for(int i=0; i<nums.length; i++){
if(visited[i]) continue;
tempList.add(nums[i]);
visited[i] = true;
helper(res,tempList,nums,visited);
visited[i] = false;
tempList.remove(tempList.size()-1);
}
}
n！比 2^n 大：
n!大于2^n
数量级比较
Leetcode 47. Permutations II. 【Medium】
在Leetcode 46 的基础上，加了一个判断。保证 nums[i]与nums[i-1]相等时，nums[i-1]总在nums[i]前面。即排除了相同数字调换顺序而产生新的元素的情况。
//还有另外的方法，比这个复杂。没掌握。
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums==null || nums.length==0) return res;
Arrays.sort(nums); //必不可少。下面的判断会用到。
boolean[] visited = new boolean[nums.length];
helper(res, nums, new ArrayList<>(), visited);
return res;
}
private void helper(List<List<Integer>> res, int[] nums, List<Integer> tempList, boolean[] visited){
if(tempList.size()==nums.length){
res.add(new ArrayList<>(tempList));
return;
}
for(int i=0; i<nums.length; i++){
if(visited[i] || (i>0 && nums[i]==nums[i-1]&&!visited[i-1])) continue; //确保对于相同的数，第i-1个数总是排在第i个数前面 (防止(1,1,2) (1,1,2)的出现)。
tempList.add(nums[i]);
visited[i] = true;
helper(res,nums,tempList,visited);
tempList.remove(tempList.size()-1);
visited[i] = false;
}
}
}
Leetcode 31. Next Permutation. 【Medium】
思路：
倒序遍历，找firstSmall。若没找到，reverse整个数组；若找到，就去找firstLarge，先swap两个数，然后reverse firstSmall后面的数组。
Time: O(n). Space: O(1).
【错误】：在找 firstSmall 和 firstLarge 的数组里，忘了写 break;
Example: [ 2,3,6,5,4,1 ]
Solution:
Step1, from right to left, find the first number which not increase in a ascending order. In this case which is 3.
Step2, here we can have two situations:
【1】We cannot find the number, all the numbers increasing in a ascending order. This means this permutation is the last permutation, we need to rotate back to the first permutation. So we reverse the whole array, for example, 6,5,4,3,2,1 we turn it to 1,2,3,4,5,6.
【2】We can find the number, then the next step, we will start from right most to leftward, try to find the first number which is larger than 3, in this case it is 4.
Then we swap 3 and 4, the list turn to 2,4,6,5,3,1.
Last, we reverse numbers on the right of 4, we finally get 2,4,1,3,5,6.
class Solution {
public void nextPermutation(int[] nums) {
if(nums == null || nums.length == 0) return;
Integer firstSmall = null;
for(int i=nums.length-2; i>=0; i--){
if(nums[i]<nums[i+1]){
firstSmall = i;
break; //一定要写这个，不然firstSmall就等于最后一个满足[i]<[i+1]的i
}
}
if(firstSmall == null){
reverse(nums,0,nums.length-1);
return;
}
Integer firstLarge = null;
for(int i=nums.length-1;i>firstSmall; i--){
if(nums[i]>nums[firstSmall]){
firstLarge = i;
break; //一定要写这个，不然firstLarge就等于最后一个满足条件的i
}
}
swap(nums,firstSmall,firstLarge);
reverse(nums,firstSmall+1,nums.length-1);
}
private void swap(int[] nums, int start, int end){
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
}
private void reverse(int[] nums, int start, int end){
while(start<end){
swap(nums,start++,end--);
}
}
}
Leetcode 60. Permutation Sequence. 【Medium】
阶乘 factorial n!
感叹号 Exclamation!
例如 n=4，从小到大的所有permutation数，应该是1xxx, 2xxx, 3xxx, 4xxx, 每种有6种(3!)可能，比如说 k=10, 由于 10/6 = 1，所以应该落在 2xxx 内；10%6 =4，应该是(1,3,4)三个数字排序得到的第4小的数；从而更新k=4，循环解决。
【1】要得到一个阶乘的数组，应该 设置 int[] factorial 来记录 n! (从1! 到 (n-1)!, 而n！是用不上的, 例子中4! 用不到，用到的是3!, 2!, ...)
【2】每次取n中的一个数之后，再从剩余的数中循环。所以需要 设置 List<Integer> nums 来记录剩下的数字。
错误1：需要设置 List<Integer> nums 和 int[] factorial。
错误2：在进入for循环前，k = k-1. 序号问题。
class Solution {
public String getPermutation(int n, int k) {
List<Integer> nums = new ArrayList<>();
for(int i=1; i<=n; i++){
nums.add(i);
}
int[] factorial = new int[n];
factorial[0] = 1;
for(int i=1; i<n; i++){
factorial[i] = i * factorial[i-1];
}
StringBuilder sb = new StringBuilder();
k = k - 1; //很重要。比如说 k = 1，其实是序号为0.
for(int i=n; i>0; i--){
int index = k / factorial[i-1];
k = k % factorial[i-1];
sb.append(nums.get(index)+"");
nums.remove(index);
}
return sb.toString();
}
}
Leetcode 205. Isomorphic Strings. 【Easy】
方法1，遍历string s, 用两个char[] 记录两个string，利用了 char可以表示为int的性质，和 array查找指定i位置的 time = O(1)的性质。【这里也可以说是O(n), HashMap通常是O(n) 以上。面试官可能认为就是O(n), 所以需要解释清楚这里的O(n) 和O(1) 的意思】
Time: O(n), Space: O(1), 因为限定死了char[] / int[]的长度。
charAt() 的时间复杂度是 O(1), deleteCharAt() 时间复杂度是O(n). 因为String，StringBuilder, StringBuffer 等的底层都是运用了 char[] 数组的方法：
https://stackoverflow.com/questions/6461402/java-charat-and-deletecharat-performance
ASCII 码：https://theasciicode.com.ar/
class Solution {
public boolean isIsomorphic(String s, String t) {
//if(s.length() != t.length()) return false;
char[] sChar = new char[128]; // int[] sChar = new int[128]; 也可以将char记录为int ; 这里128也可以写256
char[] tChar = new char[128]; // int[] tChar = new int[128]; 也可以将char记录为int ; 这里128也可以写256
//char既可以是字符char也可以是数字,一个char大小是1Byte(=8bit),存储数字范围是(-2^7,2^7-1)即(-128,127)
//而字母和数字的范围都是0-127内。0—255的ASCII码,负数会转化后再显示,如-48 将换算为 256 - 48 = 208
//常用的char都是0-127, (负数转化的)128和以上都是拉丁字母和图形符号,很少用。
for(int i=0; i<s.length(); i++){
if(sChar[s.charAt(i)] == tChar[t.charAt(i)]){
sChar[s.charAt(i)] = t.charAt(i);
tChar[t.charAt(i)] = t.charAt(i);
} else {
return false;
}
}
return true;
}
}
方法2，用 HashMap 记录，但 HashMap.containsKey() 的time = O(n), 所以time: O(n^2), Space: O(1). Space O(1) 理由是字母就在0-127内，HashMap要存储的字符map不会超过128对。 【向面试官解释清楚O(n)和O(1) 】
public boolean isIsomorphic(String s, String t) {
if((s==null&&t==null)||(s.length()==0&&t.length()==0)) return true;
HashMap<Character,Character> map = new HashMap<>();
for(int i=0; i<s.length(); i++){
char sChar = s.charAt(i); //
char tChar = t.charAt(i);
if(map.containsKey(sChar)){
if(map.get(sChar)!=tChar) return false;
} else if(map.containsValue(tChar)){
return false;
} else {
map.put(sChar,tChar);
}
}
return true;
}
Leetcode 290. Word Pattern. 【Easy】
HashMap：对应关系。
这题是string，就不能用 char[]来记录了, 直接用 HashMap, Time：O(n^2), Space: O(n). / O(1)，【需要解释清楚 O(1)含义。用于map的字母char不超过128 。】
class Solution {
public boolean wordPattern(String pattern, String str) {
if(pattern==null && str==null) return true;
String[] strs = str.split(" ");
if(pattern.length()!=strs.length) return false;
HashMap<Character, String> map = new HashMap<>();
for(int i=0; i<strs.length; i++){
if(map.containsKey(pattern.charAt(i))){
if(!map.get(pattern.charAt(i)).equals(strs[i])) return false;
} else if (map.containsValue(strs[i])){
return false;
} else {
map.put(pattern.charAt(i),strs[i]);
}
}
return true;
}
}
Leetcode 291.
由于str中无法分隔成和pattern对应的substring，所以需要用back-tracking来循环测试。构建back-tracking的helper函数，用HashMap 记录<Character, String>, helper前半部分判断map是否含有pChar的key。后半部分是for循环+back-tracking。提升的地方在于, for循环中用了map.containsKey()【O(n)】, 可以用HashSet的contains() 【O(1)】代替。
错误1，startsWith函数。
错误2，String temp2 = str.substring(strIndex, k+1); 注意k+1.
class Solution {
public boolean wordPatternMatch(String pattern, String str) {
HashMap<Character, String> map = new HashMap<>();
return helper( pattern, 0, str, 0, map);
}
private boolean helper(String pattern,int patternIndex,String str,int strIndex,HashMap<Character, String> map){
if(patternIndex == pattern.length() && strIndex == str.length()) return true;
if(patternIndex == pattern.length() || strIndex == str.length()) return false;
Character pChar = pattern.charAt(patternIndex);
if(map.containsKey(pChar)){
String temp1 = map.get(pChar);
if(!str.startsWith(temp1,strIndex)){
return false;
} else {
return helper(pattern,patternIndex+1,str,strIndex+temp1.length(),map);
}
}
for(int k=strIndex; k<str.length(); k++){
String temp2 = str.substring(strIndex, k+1);
if(map.containsValue(temp2)) continue;
map.put(pChar,temp2);
if (helper(pattern,patternIndex+1,str,strIndex+temp2.length(),map)) return true; //说明找到了
map.remove(pChar); //没找到，就remove pChar,然后尝试下一个k
}
return false; //k走到了patternIndex的尽头，还是没找到匹配的方法，就返回false
}
}
改进：在for循环的back-tracking中，用用HashSet的contains() 【O(1)】代替map.containsKey()【O(n)】。
class Solution {
public boolean wordPatternMatch(String pattern, String str) {
HashMap<Character, String> map = new HashMap<>();
HashSet<String> set = new HashSet<>();
return helper( pattern, 0, str, 0, map,set);
}
private boolean helper(String pattern,int patternIndex,String str,int strIndex,HashMap<Character, String> map,HashSet<String> set){
if(patternIndex == pattern.length() && strIndex == str.length()) return true;
if(patternIndex == pattern.length() || strIndex == str.length()) return false;
Character pChar = pattern.charAt(patternIndex);
if(map.containsKey(pChar)){
String temp1 = map.get(pChar);
if(!str.startsWith(temp1,strIndex)){
return false;
} else {
return helper(pattern,patternIndex+1,str,strIndex+temp1.length(),map,set);
}
}
for(int k=strIndex; k<str.length(); k++){
String temp2 = str.substring(strIndex, k+1);
if(set.contains(temp2)) continue;
map.put(pChar,temp2);
set.add(temp2);
if (helper(pattern,patternIndex+1,str,strIndex+temp2.length(),map,set)) return true; //说明找到了
map.remove(pChar); //没找到，就remove pChar,然后尝试下一个k
set.remove(temp2);
}
return false; //k走到了patternIndex的尽头，还是没找到匹配的方法，就返回false
}
}
Leetcode 249. Group Shifted Strings. 【Medium】
题目要找 List<List<String>>，并且每个List<String>含有相同pattern的string，我们需要设置一个HashMap<String,List<String>>来记录List<String>和它的pattern。pattern可以用两个char相减得到的多个int所组成的string来解决。设置一个getKey()方法，以fisrt char作为标志，测试distance，如果<0就+26.
关键1: 设置HashMap<String,List<String>>。
关键2：distance = distance>=0?distance:distance+26;
class Solution {
public List<List<String>> groupStrings(String[] strings) {
HashMap<String,List<String>> map = new HashMap<>();
for(String str: strings){
String key = getKey(str);
if(map.containsKey(key)){
map.get(key).add(str);
} else {
List<String> list = new ArrayList<>();
list.add(str);
map.put(key,list);
}
}
return new ArrayList<>(map.values());
}
private String getKey(HashMap<String str){
//int[] chars = new int[str.length()];
String key = new String();
for(int i=1; i<str.length(); i++){
int distance = str.charAt(i)-str.charAt(0);
distance = distance>=0?distance:distance+26;
key += distance + ",";
}
return key;
}
}
Leetcode 87. Scramble String. 【Hard】
scramble: to move with urgency or panic.
exponential: 指数 exponential growth: 指数级增长
2^31: 2 to the power of 31
recursive方法来写。for循环, 然后两个recursive判断，找到就return true。两个recursive分别是：
helper(s1前i个,s2前i个) && helper(s1剩余,s2剩余) ；
helper(s1前i个,s2后i个) && helper(s1剩余,s2剩余).
在helper()中的for循环之前，需要有int[] count + 两个for循环来判断s1和s2是否含有相同字母，这样节省time。
写helper函数。
class Solution {
public boolean isScramble(String s1, String s2) {
if(s1==null && s2==null) return true;
if(s1==null || s2==null) return false;
if(s1.length()!=s2.length()) return false;
//return true;
return helper(s1, s2);
}
private boolean helper(String s1, String s2){
if(s1.length()==0 && s2.length()==0) return true; //不是s1==null&&s2==null
if(s1.equals(s2)) return true;
int length = s1.length();
//写int[] count和两个for循环，是为了比较两个string是否含有同种类和同数量的字母,不然就return false.这样可以显著地降低time。
int[] count = new int[256];
for(int i=0; i<length; i++){
count[s1.charAt(i)]++;
count[s2.charAt(i)]--;
}
for(int i=0; i<length; i++){
if(count[s1.charAt(i)]!=0) return false;
}
for(int i=1; i<length; i++){
if(helper(s1.substring(0,i),s2.substring(0,i))&&helper(s1.substring(i),s2.substring(i))) return true;
if(helper(s1.substring(0,i),s2.substring(length-i))&&helper(s1.substring(i),s2.substring(0,length-i))) return true;
//这里的第二个if很关键，注意s1.substring(0,i)和s2.substring(length-i)的区别，就是说截取 [s1前i个] VS [s2后i个]。
}
return false;
}
}
不写helper函数。
public boolean isScramble(String s1, String s2) {
int len1 = s1.length(), len2 = s2.length();
if (len1 != len2) return false;
if (len1 == 0) return true;
// pruning
if (s1.equals(s2)) return true;
int[] count = new int[256];
for (int i = 0; i < len1; i++){
count[s1.charAt(i)]++;
count[s2.charAt(i)]--;
}
for (int i = 0; i < len1; i++){
if (count[s1.charAt(i)] != 0) return false;
}
for (int i = 1; i < len1; i++){
if (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i)))
return true;
if (isScramble(s1.substring(0, i), s2.substring(len1 - i)) && isScramble(s1.substring(i), s2.substring(0, len1 - i)))
return true;
}
return false;
}
Leetcode 17. Letter Combinations of a Phone Number. 【Medium】
遍历digits, 对于每个digit，有while+for循环，把这个digit代表的几个字母放入之前存在的String之后。要用LinkedList 而不是ArrayList, 因为 LinkedList.peek()方法是O(1), 而 ArrayList.get(ArrayList.size()-1) 是O(n).
String.toCharArray() 返回一个 char[].
关键1: String[] mapping = new String[]{"0//","1//","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
关键2: res.add("");
Leetcode 17 图解.jpg
class Solution {
public List<String> letterCombinations(String digits) {
String[] mapping = new String[]{"0//","1//","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
LinkedList<String> res = new LinkedList<>();
if(digits==null || digits.isEmpty()) return res;
res.add("");
for(int i=0; i<digits.length(); i++){
int index = digits.charAt(i) - '0'; // 或Character.getNumericValue(digits.charAt(i))
while(res.peek().length()==i){
String temp = res.remove();
for(char addChar: mapping[index].toCharArray()){
res.add(temp+addChar);
}
}
}
return res;
}
}
recursive写法 (难写)
在helper中，返回void，用temp记录暂时收集的string，index记录digits中遍历的位置。在helper内前半部分，判断index==digits.length().
class Solution {
String[] mapping = new String[]{"0//","1//","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if(digits == null || digits.isEmpty()) return res;
helper(res,digits,"",0);
return res;
}
private void helper(List<String> res,String digits, String temp, int index){
if(index==digits.length()){
res.add(temp);
return;
}
String letters = mapping[digits.charAt(index)-'0'];
for(int i=0; i<letters.length(); i++){
helper(res,digits,temp+letters.charAt(i),index+1);
}
}
}
Leetcode 320. Generalized Abbreviation. 【Medium】
recursive 做法(1)，传入固定的res和word，用temp string记录变化的string，用count记录 abbreviated character 的数量(被省略的字符的数量)，用index 记录在word中的遍历到的位置。
Time: O(2^n).
原因：Every char has two possibilities, either abbreviate it or omit it. So there are total 2^n possibilities.
public List<String> generateAbbreviations(String word) {
List<String> res = new ArrayList<>();
helper(res,word,"",0,0);
return res;
}
private void helper(List<String> res,String word,String temp,int index,int count){
if(index==word.length()){
if(count>0) temp += count;
res.add(temp);
return; //一定要写，不然会出错
}
helper(res,word,temp,index+1,count+1);
helper(res,word,temp+(count>0?count:"")+word.charAt(index),index+1,0);
}
recursive 做法(2)，区别是不传入index记录位置，而是传入去除了首字符的word，这样就不需要index记录位置了。
public List<String> generateAbbreviations(String word) {
List<String> res = new ArrayList<>();
if(word==null ) return res;
helper(res,word,"",0);
return res;
}
private void helper(List<String> res,String word,String temp,int count){
if(word.length()==0){
if(count>0) temp += count;
res.add(temp);
return;
}
helper(res,word.substring(1),temp,count+1); //不能写成count++, 因为它等价于count=count+1.不该传入一个等式作为函数参数
helper(res,word.substring(1),temp+(count>0?count:"")+word.charAt(0),0);
}
Leetcode 93. Restore IP Addresses. 【Medium】
暴力解法，写3个for循环，然后写一个判断ip Valid 的函数。
另外有back-tracking 写法，用position记录所在位置，用ipCount记录ip的数量。(其实可以不写position，而是对string s在传入下个helper之前就处理，也可以。)
关键点1：三个for循环的终止判断：j<length-1 && j<=i+3.
关键点2: back-tracking的条件判断：ipCount==4 && position==s.length()，去除最后的“.” : res.add(temp.substring(0,temp.length()-1));
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
int length = s.length();
for(int i=1; i<length-2 && i<=3; i++){
for(int j=i+1; j<length-1 && j<=i+3; j++){
for(int k=j+1; k<length && k<=j+3; k++){
String s1 = s.substring(0,i), s2=s.substring(i,j), s3=s.substring(j,k),s4=s.substring(k);
if(validAddress(s1)&&validAddress(s2)&&validAddress(s3)&&validAddress(s4)){
res.add(s1+"."+s2+"."+s3+"."+s4);
}
}
}
}
return res;
}
private boolean validAddress(String t){
if(t.length()>3 || (t.length()>1&&t.charAt(0)=='0')||(Integer.valueOf(t)>255)){ // ||t.length(==0)也可以加上,但上面的设置已经限定死了不存在这样的情况。
return false;
}
return true;
}
}
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
helper(res,s,"",0,0);
return res;
}
private void helper(List<String> res,String s,String temp,int position,int ipCount){
if(ipCount>4) return;
if(ipCount==4 && position==s.length()){
res.add(temp.substring(0,temp.length()-1));
return;
}
for(int i=1; i<4 && i+position<=s.length(); i++){
String ip = s.substring(position,position+i);
if((ip.length()>1&&ip.startsWith("0")) ||(Integer.parseInt(ip)>255)){
continue;
}
helper(res,s,temp+ip+".",position+i,ipCount+1);
}
}
Leetcode 282. Expression Add Operators. 【Hard】
Time: O(4^n). Space: O(n).
很明显的back-tracking 题目。用temp记录路径，设置 long类型的value来记录目前的计算结果，int的position记录num中经历的位置，long的preNum记录上一个数字的值(用来应对的情况)。
比如说，8-32，计算了8+3=11后，把cur值(-3)记入preNum，然后back-tracking, 遇到2，就将value=11减去preNum(-3)再加上preNum(-3)2, 即：5-(-3)+(-3)2.
8+3*2也一样。
关键点1: if(num.charAt(position)=='0' && i!=position) return; //即遇到 0XX时，在第一个X处就应该停止，这个temp不符合规范
关键点2: 记录preNum，用于计算乘法。
class Solution {
public List<String> addOperators(String num, int target) {
List<String> res = new ArrayList<>();
if(num==null || num.length()==0) return res;
helper(res,num,target,"",0,0,0);
return res;
}
private void helper(List<String> res,String num, int target,String temp,long value,int position,long preNum){
if(position==num.length()){
if(value==target) res.add(temp);
return;
}
for(int i=position; i<num.length(); i++){
if(num.charAt(position)=='0' && i!=position) return; //即遇到 0XX时，在第一个X处就应该停止，这个temp不符合规范
long cur = Long.parseLong(num.substring(position,i+1));
if(position==0){
helper(res,num,target,cur+"",value+cur,i+1,cur); //only + for position 0.
} else {
helper(res,num,target,temp+"+"+cur,value+cur,i+1,cur);
helper(res,num,target,temp+"-"+cur,value-cur,i+1,-cur);
helper(res,num,target,temp+"*"+cur,value-preNum+preNum*cur,i+1,preNum*cur);
}
}
}
}
若使用StringBuilder, 就要用setLength()函数。
public List<String> addOperators(String num, int target) {
List<String> res = new ArrayList<>();
if(num==null || num.length()==0) return res;
helper(res,num,target,new StringBuilder(),0,0,0);
return res;
}
private void helper(List<String> res,String num, int target,StringBuilder temp,long value,int position,long preNum){
if(position==num.length()){
if(value==target) res.add(temp.toString());
return;
}
for(int i=position; i<num.length(); i++){
if(num.charAt(position)=='0' && i!=position) return; //即遇到 0XX时，在第一个X处就应该停止，这个temp不符合规范
long cur = Long.parseLong(num.substring(position,i+1));
int length = temp.length();
if(position==0){
helper(res,num,target,temp.append(cur),value+cur,i+1,cur); //only + for position 0.
temp.setLength(length);
} else {
helper(res,num,target,temp.append("+"+cur),value+cur,i+1,cur);
temp.setLength(length);
helper(res,num,target,temp.append("-"+cur),value-cur,i+1,-cur);
temp.setLength(length);
helper(res,num,target,temp.append("*"+cur),value-preNum+preNum*cur,i+1,preNum*cur);
temp.setLength(length);
}
}
}
Leetcode 139. Word Break. 【Medium】【Green】
题目简介：给一个字符串和List字典，问字符串能否分割为在字典中都能查到的单词。
dp题，关键是设置boolean[] 来记录dp[j]，从而知道在 j 之前是否都能找到单词。两个for循环就解决。
做法1，用 List.contains()操作，Time O(n^3), 不推荐。
Time: O(n^3), 因为List.contains()是O(n)的 (String.substring()方法是O(1))。
Space: O(n).
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length()+1];
dp[0]=true;
for(int i=1; i<=s.length();i++){
for(int j=0; j<i; j++){
if(dp[j] && wordDict.contains(s.substring(j,i))){
dp[i] = true;
break;
}
}
}
return dp[dp.length-1];
}
}
改进：用 set 来实现 set.contains()。
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>();
set.addAll(wordDict);
boolean[] dp = new boolean[s.length()+1];
dp[0]=true;
for(int i=1; i<=s.length();i++){
for(int j=i-1; j>=0; j--){ //倒序遍历，会比顺序遍历好, improve performance.
if(dp[j] && set.contains(s.substring(j,i))){
dp[i] = true;
break;
}
}
}
return dp[dp.length-1];
}
}
类似做法一，以下是dp的典型写法，for循环遍历其中一个input： String s, 另一个for循环遍历另外的一个input：wordDict。
String.equals()是O(n)，但这里word的长度可以认为是一个常数，与s.length()没关系。所以: Time: O(m*n)，或者说O(n^2).
缺点是wordDict过大的话会麻烦。
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
// 从这个位置向前考虑能否match某个word，如果match并且前面也为true的话，那么这一段我们可以将其设置为true
for (String word : wordDict) {
// 至少i要在word之后吧，如果这个位置根本放不下这个word，那就下一个
if ( i >= word.length() && dp[i - word.length()] && word.equals(s.substring(i - word.length(),i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
Leetcode 140. Word Break II. 【Hard】
用每个word来测试是否startsWith(), 若true，就记录next，然后判断next是否为空，若为空，就add s，不为空，就backtrack()。如果没有写map, 逻辑上可行，但会超时。所以需要加上map，来记录已经遍历的 截去前面一部分的substring有几个可能性。map：new HashMap<String, List<String>>()，比如("catsanddog",res)，res=("cat sand dog","cats and dog")
没写map的代码：
public List<String> wordBreak(String s, List<String> wordDict) {
return backtrack(s,wordDict);
}
// backtrack returns an array including all substrings derived from s.
public List<String> backtrack(String s, List<String> wordDict){
//if(map.containsKey(s)) return map.get(s);
List<String> result = new ArrayList<String>();
for(String word: wordDict){
if(s.startsWith(word)) {
String next = s.substring(word.length());
if(next.length()==0){
result.add(word);
} else for(String subStr: backtrack(next, wordDict)) {
result.add(word+" "+subStr);
}
}
}
//map.put(s, result);
return result;
}
最简洁的答案：
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
return backtrack(s,wordDict,new HashMap<String, List<String>>());
}
// backtrack returns an array including all substrings derived from s.
public List<String> backtrack(String s, List<String> wordDict, Map<String,List<String>> map){
if(map.containsKey(s)) return map.get(s);
List<String> result = new ArrayList<String>();
for(String word: wordDict){
if(s.startsWith(word)) {
String next = s.substring(word.length());
if(next.length()==0){
result.add(word);
} else for(String subStr: backtrack(next, wordDict, map)) {
result.add(word+" "+subStr);
}
}
}
map.put(s, result);
return result;
}
}
分析1:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
s="catsanddog", NEW res,
(1)word=cat, next=sanddog,
backtrack1()得到list ("sand dog"),subStr处理,得到res("cat sand dog"),
backtrack1(), word=sand,next=dog,backtrack2()得到的是含有("dog")的List,对于每一个subStr,add进当前res,有res("sand dog"),map.put("sanddog",res),return res返回上一级
backtrack2(), s=dog, word=dog, next="",res.add("dog"),map.add("dog",res),return res返回上一级
(2)word=cats,next=anddog,backtrackA(),
backtrackA(), 得到("and dog")的list,subStr处理，res原基础("cat sand dog")上加入"cats and dog"
backtrackA(),word=and,next=dog,backtrackB()得到含有("dog")的List,有res("and dog"),map.put("anddog",res),return res返回上一级
backtrackB(),返回map.get("dog")
map.put("catsanddog",res) (res两个元素，"cat sand dog"和"cats and dog")
return res，就是答案
分析2：
s= "catsandcatsand"
dict = ["cat","cats","and","sand","dog"]
s="catsandcatsand", NEW res, (1)word=cat, next=sandcatsand,
backtrack1()得到list ("sand cat sand","sand cats and"),subStr处理,得到res("cat sand cat sand","cat sand cats and"),map.put("catsandcatsand",res)
backtrack1(), word=sand,next=catsand,backtrack2()得到的是含有("cat sand","cats and")的List,对于每一个subStr,add进当前res,有res("sand cat sand","sand cats and"),map.put("sandcatsand",res),return res返回上一级
backtrack2(), s=catsand,(1)word=cat,next=sand,下一级完成后res.add("cat sand"),res有("cat sand"),检验其他word
(2)word=cats,next=and,下一级完成后res.add("cats and"),res有("cat sand","cats and"),map.put("catsand",res)返回上一级
backtrack3(), (1)s=sand,word=sand,next="",result.add("sand"),map.put("sand",result) return res返回上一级
(2)s=and,word=and,next="",res.add("and"),map.put("and",result) return res返回上一级
(2) word = cats, next=andcatsand, backtrackA(),把subStr加入到res,res.ADD("cats and cat sand","cats and cats and")
backtrackA(),s=andsand,word=and,next=catsand,backtrackB()得到"cat sand","cats and"
backtrackB(),s=catsand,返回map.get("catsand")
map.put("catsandcatsand",res),res含有："cat sand cat sand","cat sand cats and","cats and cat sand","cats and cats and"
RETURN res
网友评论