Chapter five Depth First Search（深度优先搜索）

组合搜索问题 Combination

问题模型：求出所有满足条件的“组合”。判断条件：组合中的元素是顺序无关的。时间复杂度：与 2^n 相关。

1.Chapter one 第2题 subsets(子集）

2.Chapter one 第3题 subsets-ii(子集II）

3.combination-sum（数字组合）

给出一组候选数字(C)和目标数字(T),找到C中所有的组合，使找出的数字和为T。C中的数字可以无限制重复被选取。所有的数字(包括目标数字)均为正整数。元素组合(a1, a2, … , ak)必须是非降序(ie, a1 ≤ a2 ≤ … ≤ ak)。解集不能包含重复的组合。

例如,给出候选数组[2,3,6,7]和目标数字7，解集为：[[7],[2,2,3]]

public class Solution {
    /**
     * @param candidates: A list of integers
     * @param target:An integer
     * @return: A list of lists of integers
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // write your code here
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        if (candidates == null || candidates.length == 0) {
            return results;
        }
        Arrays.sort(candidates);
        List<Integer> combination = new ArrayList<Integer>();
        dfs(candidates, 0, target, combination, results);
        return results;
    }
    private void dfs(int[] candidates,
                     int index,
                     int target,
                     List<Integer> combination,
                     List<List<Integer>> results) {
        if (target == 0) {
            results.add(new ArrayList<Integer>(combination));
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            if (i != index && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (candidates[i] > target) {
                break;
            }
            combination.add(candidates[i]);
            dfs(candidates, i, target - candidates[i], combination, results);
            combination.remove(combination.size() - 1);
        }
    }
}

4.combination-sum-ii（数字组合II）

给出一组候选数字(C)和目标数字(T),找出C中所有的组合，使组合中数字的和为T。C中每个数字在每个组合中只能使用一次。所有的数字(包括目标数字)均为正整数。元素组合(a1, a2, … , ak)必须是非降序(ie, a1 ≤ a2 ≤ … ≤ ak)。解集不能包含重复的组合。

例如，给出候选数字集合[10,1,6,7,2,1,5] 和目标数字 8  ,解集为：[[1,7],[1,2,5],[2,6],[1,1,6]]

public class Solution {
    /**
     * @param num: Given the candidate numbers
     * @param target: Given the target number
     * @return: All the combinations that sum to target
     */
    public List<List<Integer>> combinationSum2(int[] num, int target) {
        // write your code here
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        if (num == null || num.length == 0) {
            return results;
        }
        Arrays.sort(num);
        List<Integer> combination = new ArrayList<Integer>();
        dfs(num, 0, target, combination, results);
        return results;
    }
    private void dfs(int[] num,
                     int index,
                     int target,
                     List<Integer> combination,
                     List<List<Integer>> results) {
        if (target == 0) {
            results.add(new ArrayList<Integer>(combination));
            return;
        }
        for (int i = index; i < num.length; i++) {
            if (i != index && num[i] == num[i - 1]) {
                continue;
            }
            if (num[i] > target) {
                break;
            }
            combination.add(num[i]);
            dfs(num, i + 1, target - num[i], combination, results);
            combination.remove(combination.size() - 1);
        }
    }
}

第3题和第4题的区别只在于C中的每个数字可以使用几次，故第3题搜索从index开始：dfs(candidates, i, target - candidates[i], combination, results);第4题从index+1开始：dfs(num, i + 1, target - num[i], combination, results)。两题的共同点在解集不能包含重复的组合，故使用“选代表法”去重：if (i != index && candidates[i] == candidates[i - 1]) {continue;}

5.palindrome-partitioning（分割回文串）

给定一个字符串s，将s分割成一些子串，使每个子串都是回文串。返回s所有可能的回文串分割方案。

给出 s = "aab"，返回[["aa", "b"],["a", "a", "b"]]

DFS通常解法：

public class Solution {
    /**
     * @param s: A string
     * @return: A list of lists of string
     */
    public List<List<String>> partition(String s) {
        // write your code here
        List<List<String>> results = new ArrayList<List<String>>();
        if (s == null || s.length() == 0) {
            return results;
        }
        List<String> partition = new ArrayList<String>();
        dfs(s, 0, partition, results);
        return results;
    }
    private void dfs(String s,
                     int startIndex,
                     List<String> partition,
                     List<List<String>> results) {
        if (startIndex == s.length()) {
            results.add(new ArrayList<String>(partition));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            String subString = s.substring(startIndex, i + 1);
            if (!isPalindrome(subString)) {
                continue;
            }
            partition.add(subString);
            dfs(s, i + 1, partition, results);
            partition.remove(partition.size() - 1);
        }
    }
    private boolean isPalindrome(String s) {
        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

注意：从startIndex（初始为0）位置开始截取（startIndex, i+ 1）长度的子字符串判断是否为回文串，如果不是就i++，如果是就进行下一层dfs。结束条件为startIndex=s.length()-1

优化回文串判断的解法：

public class Solution {
    List<List<String>> results;
    boolean[][] isPalindrome;
    /**
     * @param s: A string
     * @return: A list of lists of string
     */
    public List<List<String>> partition(String s) {
        results = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return results;
        }
        getIsPalindrome(s);
        helper(s, 0, new ArrayList<Integer>());
        return results;
    }
    private void getIsPalindrome(String s) {
        int n = s.length();
        isPalindrome = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            isPalindrome[i][i] = true;
        }
        for (int i = 0; i < n - 1; i++) {
            isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
        }
        for (int i = n - 3; i >= 0; i--) {
            for (int j = i + 2; j < n; j++) {
                isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
            }
        }
    }
    private void helper(String s,
                        int startIndex,
                        List<Integer> partition) {
        if (startIndex == s.length()) {
            addResult(s, partition);
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (!isPalindrome[startIndex][i]) {
                continue;
            }
            partition.add(i);
            helper(s, i + 1, partition);
            partition.remove(partition.size() - 1);
        }
    }
    private void addResult(String s, List<Integer> partition) {
        List<String> result = new ArrayList<>();
        int startIndex = 0;
        for (int i = 0; i < partition.size(); i++) {
            result.add(s.substring(startIndex, partition.get(i) + 1));
            startIndex = partition.get(i) + 1;
        }
        results.add(result);
    }
}

注意：动态规划也可以判断回文字符串，回文串的子串也是回文串，比如p[i,j](表示以i开始以j结束的子串)是回文字符串，那么p[i+1,j-1]也是回文字符串。

int n = s.length();
boolean[][] isPalindrome = new boolean[n][n];
for (int i = 0; i < n; i++) {
    isPalindrome[i][i] = true;
}
for (int i = 0; i < n - 1; i++) {//判断相邻两个字符是否是回文串
    isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
}
for (int i = n - 3; i >= 0; i--) {//判断其余字符
    for (int j = i + 2; j < n; j++) {
        isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
    }
}

6.palindrome-partitioning-ii（分割回文串II）

给定一个字符串s，将s分割成一些子串，使每个子串都是回文。返回s符合要求的的最少分割次数。

解法1：

public class Solution {
    /**
     * @param s a string
     * @return an integer
     */
    private boolean[][] getIsPalindrome(String s) {
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            isPalindrome[i][i] = true;
        }
        for (int i = 0; i < n - 1; i++) {
            isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
        }
        for (int i = n - 3; i >= 0; i--) {
            for (int j = i + 2; j < n; j++) {
                isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
            }
        }
        return isPalindrome;
    }
    public int minCut(String s) {
        // write your code here
        if (s == null || s.length() == 0) {
            return 0;
        }
        boolean[][] isPalindrome = getIsPalindrome(s);
        int[] f = new int[s.length() + 1];
        f[0] = 0;
        for (int i = 1; i <= s.length(); i++) {
            f[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (isPalindrome[j][i - 1]) {
                    f[i] = Math.min(f[i], f[j] + 1);
                }
            }
        }
        return f[s.length()] - 1;
    }
};

注意：使用动态规划判断回文字符串。f[i]表示前i个字母最少可以被分割为多少个回文串，返回f[n]-1(分割的次数）。

if (isPalindrome[j][i - 1]) {//从j到i - 1的子串是回文串
       f[i] = Math.min(f[i], f[j] + 1);//取f[i]和f[j] + 1（位置j+1处的字母为单独一个回文串）中较小的那个
}

解法2：

public class Solution {
    /**
     * @param s a string
     * @return an integer
     */
    private boolean[][] getIsPalindrome(String s) {
        boolean[][] isPalindrome = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            isPalindrome[i][i] = true;
        }
        for (int i = 0; i < s.length() - 1; i++) {
            isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
        }
        for (int length = 2; length < s.length(); length++) {
            for (int start = 0; start + length < s.length(); start++) {
                isPalindrome[start][start + length]
                    = isPalindrome[start + 1][start + length - 1] && s.charAt(start) == s.charAt(start + length);
            }
        }
        return isPalindrome;
    }
    public int minCut(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        boolean[][] isPalindrome = getIsPalindrome(s);
        int[] f = new int[s.length() + 1];
        for (int i = 0; i <= s.length(); i++) {
            f[i] = i - 1;
        }
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (isPalindrome[j][i - 1]) {
                    f[i] = Math.min(f[i], f[j] + 1);
                }
            }
        }
        return f[s.length()];
    }
};

注意：使用动态规划判断回文字符串。f[i]表示前i个字母最少被切割几次可以分割为都是回文串，返回f[n](分割的次数）。

        与解法1的主要区别是在f[i]赋初值上的变化。解法1:f[i]=i;解法2：f[i]=i-1。返回值相应也有区别。f[i]初始化都为int[] f = new int[s.length() + 1];

排列搜索问题 Permutation

问题模型：求出所有满足条件的“ 排列”。判断条件：组合中的元素是顺序“ 相关”的。时间复杂度：与 n! 相关。

7.Chapter one 第4题 permutations(全排列）

8.Chapter one 第5题 permutations-ii（带重复元素的排列）

9.n-queens（N皇后）

n皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击（任意两个皇后都不能放在同一行、同一列或同一斜线上）。给定一个整数n，返回所有不同的n皇后问题的解决方案。每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。

class Solution {
    /**
     * Get all distinct N-Queen solutions
     * @param n: The number of queens
     * @return: All distinct solutions
     * For example, A string '...Q' shows a queen on forth position
     */
    ArrayList<ArrayList<String>> solveNQueens(int n) {
        // write your code here
        ArrayList<ArrayList<String>> results = new ArrayList<ArrayList<String>>();
        if (n <= 0) {
            return results;
        }
        search(results, new ArrayList<Integer>(), n);
        return results;
    }
    //寻找皇后放置的合适位置（cols存储每一行的列索引）
    private void search(ArrayList<ArrayList<String>> results,
                        ArrayList<Integer> cols,
                        int n) {
        if (cols.size() == n) {
            results.add(drawChessBoard(cols));
            return;
        }
        for (int colIndex = 0; colIndex < n; colIndex++) {
            if (!isValid(cols, colIndex)) {
                continue;
            }
            cols.add(colIndex);
            search(results, cols, n);
            cols.remove(cols.size() - 1);
        }
    }
    //绘制棋盘
    private ArrayList<String> drawChessBoard(ArrayList<Integer> cols) {
        ArrayList<String> chessboard = new ArrayList<String>();
        for (int i = 0; i < cols.size(); i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < cols.size(); j++) {
                sb.append(j == cols.get(i) ? "Q" : ".");
            }
            chessboard.add(sb.toString());
        }
        return chessboard;
    }
    //判断位置是否有效
    private boolean isValid(ArrayList<Integer> cols, int column) {
        int row = cols.size();
        for (int rowIndex = 0; rowIndex < cols.size(); rowIndex++) {
            if (cols.get(rowIndex) == column) {
                return false;
            }
            if (rowIndex + cols.get(rowIndex) == row + column) {
                return false;
            }
            if (rowIndex - cols.get(rowIndex) == row - column) {
                return false;
            }
        }
        return true;
    }
};

注意：cols存储的是每一行放置皇后的列索引。search()函数寻找每一行中皇后放置的合适位置，列索引存储在cols中；drawChessBoard()函数绘制棋盘，皇后的位置绘制"Q"，其余位置绘制".:,要使用StringBuilder； isValid()函数判断该位置是否有效。

10.word-ladder-ii（单词接龙II）【hard】（Chapter four 第20题 word-ladder）

给出两个单词（start和end）和一个字典，找出所有从start到end的最短转换序列。每次只能改变一个字母。变换过程中的中间单词必须在字典中出现。所有单词具有相同的长度。所有单词都只包含小写字母。

public class Solution {
    /**
      * @param start, a string
      * @param end, a string
      * @param dict, a set of string
      * @return a list of lists of string
      */
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        // write your code here
        List<List<String>> ladders = new ArrayList<List<String>>();
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        Map<String, Integer> distance = new HashMap<String, Integer>();
        dict.add(start);
        dict.add(end);
        bfs(map, distance, start, end, dict);
        List<String> path = new ArrayList<String>();
        dfs(ladders, path, end, start, distance, map);
        return ladders;
    }
    void dfs(List<List<String>> ladders, List<String> path, String crt,
            String start, Map<String, Integer> distance,
            Map<String, List<String>> map) {
        path.add(crt);
        if (crt.equals(start)) {
            Collections.reverse(path);
            ladders.add(new ArrayList<String>(path));
            Collections.reverse(path);
        } else {
            for (String next : map.get(crt)) {
                if (distance.containsKey(next) && distance.get(crt) == distance.get(next) + 1) { 
                    dfs(ladders, path, next, start, distance, map);
                }
            }
        }
        path.remove(path.size() - 1);
    }
    void bfs(Map<String, List<String>> map, Map<String, Integer> distance,
            String start, String end, Set<String> dict) {
        Queue<String> q = new LinkedList<String>();
        q.offer(start);
        distance.put(start, 0);
        for (String s : dict) {
            map.put(s, new ArrayList<String>());
        }
        while (!q.isEmpty()) {
            String crt = q.poll();
            List<String> nextList = expand(crt, dict);
            for (String next : nextList) {
                map.get(next).add(crt);
                if (!distance.containsKey(next)) {
                    distance.put(next, distance.get(crt) + 1);
                    q.offer(next);
                }
            }
        }
    }
    List<String> expand(String crt, Set<String> dict) {
        List<String> expansion = new ArrayList<String>();
        for (int i = 0; i < crt.length(); i++) {
            for (char ch = 'a'; ch <= 'z'; ch++) {
                if (ch != crt.charAt(i)) {
                    String expanded = crt.substring(0, i) + ch
                            + crt.substring(i + 1);
                    if (dict.contains(expanded)) {
                        expansion.add(expanded);
                    }
                }
            }
        }
        return expansion;
    }
}

11.string-permutation（字符串置换）

给定两个字符串，请设计一个方法来判定其中一个字符串是否为另一个字符串的置换。置换的意思是，通过改变顺序可以使得两个字符串相等。

public class Solution {
    /**
     * @param A a string
     * @param B a string
     * @return a boolean
     */
    public boolean stringPermutation(String A, String B) {
        // Write your code here
        int[] cnt = new int[1000];
        for (int i = 0; i < A.length(); i++) {
            cnt[(int) A.charAt(i)]++;
        }
        for (int j = 0; j < B.length(); j++) {
            cnt[(int) B.charAt(j)]--;
        }
        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

注意：使用一个数组，遍历A使得数组中相应位置的元素加1， 遍历B使得数组中相应位置的元素减1， 若最终数组中存在不为0的数则返回false。

12.permutation-index（排列序号）

给出一个不含重复数字的排列，求这些数字的所有排列按字典序排序后该排列的编号。其中，编号从1开始。

public class Solution {
    /**
     * @param A an integer array
     * @return a long integer
     */
    long fac(int numerator) {
        long now = 1;
        for (int i = 1; i <= numerator; i++) {
            now *= (long) i;
        }
        return now;
    }
    long generateNum(HashMap<Integer, Integer> hash) {
        long denominator = 1;
        int sum = 0;
        for (int val : hash.values()) {
            if (val == 0) {    
                continue;
            }
            denominator *= fac(val);
            sum += val;
        }
        if (sum == 0) {
            return sum;
        }
        return fac(sum) / denominator;
    }
    public long permutationIndex(int[] A) {
        // Write your code here
        HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
        for (int i = 0; i < A.length; i++) {
            if (hash.containsKey(A[i])) {
                hash.put(A[i], hash.get(A[i]) + 1);
            }
            else {
                hash.put(A[i], 1);
            }
        }
        long ans = 0;
        for (int i = 0; i < A.length; i++) {
            for (int j = i + 1; j < A.length; j++) {
                if (A[j] < A[i]) {
                    hash.put(A[j], hash.get(A[j]) - 1);
                    ans += generateNum(hash);
                    hash.put(A[j], hash.get(A[j]) + 1);
                }
            }
            hash.put(A[i], hash.get(A[i]) - 1);
        }
        return ans + 1;
    }
}

13.permutation-index-ii（排列序号II）

给出一个可能包含重复数字的排列，求这些数字的所有排列按字典序排序后该排列在其中的编号。编号从1开始。

方法一：

public class Solution {
    /**
     * @param A an integer array
     * @return a long integer
     */
    long fac(int numerator) {
        long now = 1;
        for (int i = 1; i <= numerator; i++) {
            now *= (long) i;
        }
        return now;
    }
    long generateNum(HashMap<Integer, Integer> hash) {
        long denominator = 1;
        int sum = 0;
        for (int val : hash.values()) {
            if (val == 0) {
                continue;
            }
            denominator *= fac(val);
            sum += val;
        }
        if (sum == 0) {
            return sum;
        }
        return fac(sum) / denominator;
    }
    public long permutationIndexII(int[] A) {
        HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
        for (int i = 0; i < A.length; i++) {
            if (hash.containsKey(A[i])) {
                hash.put(A[i], hash.get(A[i]) + 1);
            } else {
                hash.put(A[i], 1);
            }
        }
        long ans = 0;
        for (int i = 0; i < A.length; i++) {
            HashMap<Integer, Integer> flag = new HashMap<Integer, Integer>();
            for (int j = i + 1; j < A.length; j++) {
                if (A[j] < A[i] && !flag.containsKey(A[j])) {
                    flag.put(A[j], 1);
                    hash.put(A[j], hash.get(A[j]) - 1);
                    ans += generateNum(hash);
                    hash.put(A[j], hash.get(A[j]) + 1);
                }
            }
            hash.put(A[i], hash.get(A[i]) - 1);
        }
        return ans + 1;
    }
}

方法二：

public class Solution {
    /**
     * @param A an integer array
     * @return a long integer
     */
    public long permutationIndexII(int[] A) {
        // Write your code here
        if (A == null || A.length == 0) {
            return 0L;
        }
        Map<Integer, Integer> counter = new HashMap<Integer, Integer>();
        long index = 1;
        long fact = 1;
        long multiFact = 1;
        for (int i = A.length - 1; i >= 0; i--) {
            if (counter.containsKey(A[i])) {
                counter.put(A[i], counter.get(A[i]) + 1);
                multiFact *= counter.get(A[i]);
            } else {
                counter.put(A[i], 1);
            }
            int rank = 0;
            for (int j = i + 1; j < A.length; j++) {
                if (A[i] > A[j]) {
                    rank++;
                }
            }
            index += rank * fact / multiFact;
            fact *= (A.length - i);
        }
        return index;
    }
}

14.next-permutation（下一个排列）

给定一个整数数组来表示排列，找出其之后的一个排列。排列中可能包含重复的整数。

public class Solution {
    /**
     * @param nums: an array of integers
     * @return: return nothing (void), do not return anything, modify nums in-place instead
     */
    public void reverse(int[] num, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            int temp = num[i];
            num[i] = num[j];
            num[j] = temp;
        }
    }
    public int[] nextPermutation(int[] nums) {
        // write your code here
        // find the last increase index
        int index = -1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                index = i;
                break;
            }
        }
        if (index == -1) {
            reverse(nums, 0, nums.length - 1);
            return nums;
        }
        // find the first bigger one
        int  biggerIndex = index + 1;
        for (int i = nums.length - 1; i > index; i--) {
            if (nums[i] > nums[index]) {
                biggerIndex = i;
                break;
            }
        }
        // swap them to make the permutation bigger
        int temp = nums[index];
        nums[index] = nums[biggerIndex];
        nums[biggerIndex] = temp;
        // reverse the last part
        reverse(nums, index + 1, nums.length - 1);
        return nums;
    }
}

注意：[1,2,7,4,3,1]的下一个排列是[1,3,1,2,4,7] 通过观察原数组可以发现，如果1.从末尾往前看，数字逐渐变大，到了2时才减小。再2.从后往前找第一个比2大的数字是3，3.交换2和3，再4.把此时3后面的所有数字转置一下即可。[1,2,7,4,3,1]->[1,2,7,4,3,1]->[1,3,7,4,2,1]->[1,3,1,2,4,7]

首先从后往前找到num[index]<num[index+1]的位置index（初始值为-1）, 如果index=-1，说明数组为从大到小的排列，则下一个排列为从小到大。如果index！= -1，再从后往前寻找num[biggerIndex]>num[index]的位置biggerIndex（初始值为index + 1）,然后交换两个位置的元素，将index+1到排列最后的所有元素翻转即可。

15.next-permutation-ii（下一个排列II）

给定一个若干整数的排列，给出按正数大小进行字典序从小到大排序后的下一个排列。如果没有下一个排列，则输出字典序最小的序列。

public class Solution {
    /**
     * @param nums: an array of integers
     * @return: return nothing (void), do not return anything, modify nums in-place instead
     */
    public void reverse(int[] num, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            int temp = num[i];
            num[i] = num[j];
            num[j] = temp;
        }
    }
    public void nextPermutation(int[] nums) {
        // write your code here
        // find the last increase index
        int index = -1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                index = i;
                break;
            }
        }
        if (index == -1) {
            reverse(nums, 0, nums.length - 1);
            return;
        }
        // find the first bigger one
        int biggerIndex = index + 1;
        for (int i = nums.length - 1; i > index; i--) {
            if (nums[i] > nums[index]) {
                biggerIndex = i;
                break;
            }
        }
        while (biggerIndex - 1 > index && nums[biggerIndex] == nums[biggerIndex - 1]) {
            biggerIndex--;
        }
        // swap them to make the permutation bigger
        int temp = nums[index];
        nums[index] = nums[biggerIndex];
        nums[biggerIndex] = temp;
        // reverse the last part
        reverse(nums, index + 1, nums.length - 1);
    }
}

注意：在交换index和biggerIndex位置的元素前，要先判断biggerIndex是否可以减小。

while (biggerIndex - 1 > index && nums[biggerIndex] == nums[biggerIndex - 1]) {biggerIndex--;}

16.previous-permutation（上一个排列）

给定一个整数数组来表示排列，找出其上一个排列。排列中可能包含重复的整数。

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers that's previous permuation
     */
    private void swapItem(ArrayList<Integer> nums, int i, int j) {
        Integer temp = nums.get(i);
        nums.set(i, nums.get(j));
        nums.set(j, temp);
    }
    private void swapList(ArrayList<Integer> nums, int i, int j) {
        while (i < j) {
            swapItem(nums, i, j);
            i++;
            j--;
        }
    }
    public ArrayList<Integer> previousPermuation(ArrayList<Integer> nums) {
        // write your code
        int len = nums.size();
        if (len <= 1) {
            return nums;
        }
        //从后往前找到数字不再减小的位置i nums.get(i) < nums.get(i-1)
        int i = len - 1;
        while (i > 0 && nums.get(i) >= nums.get(i - 1)) {
            i--;
        }
        //翻转位置i到排序末尾的元素
        swapList(nums, i, len - 1);
        //在位置i到排列末尾的元素中从前往后找第一个比位置i-1小的元素nums.get(j) < nums.get(i-1)
        if (i != 0) {
            int j = i;
            while (nums.get(j) >= nums.get(i - 1)) {
                j++;
            }
            //交换位置j和位置i-1的元素
            swapItem(nums, j, i - 1);
        }
        return nums;
    }
}

注意：思路跟第13题正好相反。如果数组的长度<=1直接返回，首先从后往前找到数字不再减小的位置i，nums.get(i) < nums.get(i-1)；然后翻转位置i到排序末尾的元素；如果i!=0,接着在位置i到排列末尾的元素中从前往后找第一个比位置i-1小的元素位置为j, nums.get(j) < nums.get(i-1)；最后交换位置j和位置i-1的元素。[1,3,1,2,4,7]->[1,3,7,4,2,1]->[1,3,7,4,2,1]->[1,2,7,4,3,1]

ArrayList<Integer> nums)：nums.size()求长度， nums.get()取元素，nums.set()赋元素值。

17.string-permutation-ii（字符串的不同排列）

给出一个字符串，找到它的所有排列，注意同一个字符串不要打印两次。

public class Solution {
    /*
     * @param : A string
     * @return: all permutations
     */
    public List<String> stringPermutation2(String str) {
        // write your code here
        List<String> result = new ArrayList<String>();
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        result.add(String.valueOf(chars));
        while ((chars = nextPermutation(chars)) != null) {
            result.add(String.valueOf(chars));
        }
        return result;
    }
    public char[] nextPermutation(char[] nums) {
        int index = -1;
        for (int i = nums.length - 1; i > 0; i--){
            if (nums[i] > nums[i - 1]){
                index = i - 1;
                break;
            }
        }
        if (index == -1){
            return null;
        }
        for (int i = nums.length - 1; i > index; i--){
            if (nums[i] > nums[index]){
                char temp = nums[i];
                nums[i] = nums[index];
                nums[index] = temp;
                break;
            }
        }
        reverse(nums, index + 1, nums.length - 1);
        return nums;
    }
    public void reverse(char[] num, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            char temp = num[i];
            num[i] = num[j];
            num[j] = temp;
        }
    }
};

注意：首先将给定字符串str转换成char数组排序后放入结果集，然后套用 下一个排列 题目中的4个步骤寻找其余结果。

string转换为char：String str = "abc";char[] chars = str.toCharArray();

char转换为string：char[] chars = {"a","b","c"}; String str = String.valueOf(chars)或 String str = new String(chars);

18.word-break（单词划分）

给出一个字符串s和一个词典，判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。

public class Solution {
    /**
     * @param s: A string s
     * @param dict: A dictionary of words dict
     */
    private int getMaxLength(Set<String> dict) {
        int maxLength = 0;
        for (String s : dict) {
            maxLength = Math.max(maxLength, s.length());
        }
        return maxLength;
    }
    public boolean wordBreak(String s, Set<String> dict) {
        // write your code here
        if (s == null || s.length() == 0) {
            return true;
        }
        int maxLength = getMaxLength(dict);
        boolean[] canSegment = new boolean[s.length() + 1];
        canSegment[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            canSegment[i] = false;
            for (int lastWordLength = 1;
                lastWordLength <= maxLength && lastWordLength <= i;
                lastWordLength++) {
                if (!canSegment[i - lastWordLength]) {
                    continue;
                }
                String word = s.substring(i - lastWordLength, i);
                if (dict.contains(word)) {
                    canSegment[i] = true;
                    break;
                }
            }
        }
        return canSegment[s.length()];
    }
}

注意：boolean型数组canSegment[]记录某个位置（从0到s.length()）是否可以切分，boolean[] canSegment = new boolean[s.length() + 1]。最终返回结果为canSegment[s.length()]，即整个字符串是否可以切分。要求出词典dict中的最大单词长度maxLength,划分单词的最大长度不能超过maxLength。

for (int i = 1; i <= s.length(); i++) {
    canSegment[i] = false;//初始化都为flase(不能切分)
    for (int lastWordLength = 1;lastWordLength <= maxLength && lastWordLength <= i;lastWordLength++) {
           if (!canSegment[i - lastWordLength]) {
                continue;
           }
           String word = s.substring(i - lastWordLength, i);//取可以划分的单词word
           if (dict.contains(word)) {//如果字典中包含此单词
               canSegment[i] = true;
               break;
          }
     }
}

19.word-break-ii（单词划分II）【hard】

给定一个字符串s和一个单词字典dict，在s中添加空格来构造一个句子，其中每个单词都是有效的字典单词。返回所有这样的句子。

方法一：

public class Solution {
    /**
     * @param s a string
     * @param wordDict a set of words
     */
    private void search(int index, String s, List<Integer> path,
                   boolean[][] isWord, boolean[] possible,
                   List<String> result) {
        if (!possible[index]) {
            return;
        }
        if (index == s.length()) {
            StringBuilder sb = new StringBuilder();
            int lastIndex = 0;
            for (int i = 0; i < path.size(); i++) {
                sb.append(s.substring(lastIndex, path.get(i)));
                if (i != path.size() - 1) {
                    sb.append(" ");
                }
                lastIndex = path.get(i);
            }
            result.add(sb.toString());
            return;
        }
        for (int i = index; i < s.length(); i++) {
            if (!isWord[index][i]) {
                continue;
            }
            path.add(i + 1);
            search(i + 1, s, path, isWord, possible, result);
            path.remove(path.size() - 1);
        }
    }
    public List<String> wordBreak(String s, Set<String> wordDict) {
        ArrayList<String> result = new ArrayList<String>();
        if (s.length() == 0) {
            return result;
        }
        boolean[][] isWord = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                String word = s.substring(i, j + 1);
                isWord[i][j] = wordDict.contains(word);
            }
        }
        boolean[] possible = new boolean[s.length() + 1];
        possible[s.length()] = true;
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (isWord[i][j] && possible[j + 1]) {
                    possible[i] = true;
                    break;
                }
            }
        }
        List<Integer> path = new ArrayList<Integer>();
        search(0, s, path, isWord, possible, result);
        return result;
    }
}

方法二：

public class Solution {
    /**
     * @param s a string
     * @param wordDict a set of words
     */
    public List<String> wordBreak(String s, Set<String> wordDict) {
        // Write your code here
        // Note: The Solution object is instantiated only once and is reused by each test case.
        Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        return wordBreakHelper(s, wordDict, map);
    }
    public ArrayList<String> wordBreakHelper(String s,
                                             Set<String> dict,
                                             Map<String, ArrayList<String>> memo){
        if (memo.containsKey(s)) {
            return memo.get(s);
        }
        ArrayList<String> result = new ArrayList<String>();
        int n = s.length();
        if (n <= 0) {
            return result;
        }
        for (int len = 1; len <= n; ++len){
            String subfix = s.substring(0, len);
            if (dict.contains(subfix)){
                if (len == n) {
                    result.add(subfix);
                } else {
                    String prefix = s.substring(len);
                    ArrayList<String> tmp = wordBreakHelper(prefix, dict, memo);
                    for (String item : tmp) {
                        item = subfix + " " + item;
                        result.add(item);
                    }
                }
            }
        }
        memo.put(s, result);
        return result;
    }
}