常见搜索问题的迭代解法

从搜索树结构上讲，这类问题所有解的构造方式呈现 BFS 的分层结构，可以手动建立分层处理的机制处理。与之相对的，最常见的递归解法是从 DFS 的角度去探索状态空间。

搜索问题的迭代解法主要分这么两种，取决于最终解的构造方式，也即 F(n) 和 F(n - 1) 之间的关系。

• append 类

  • 比如 subsets 中，每次迭代出现的新解，都是由新元素 append 到已知解的后面构造出来的；(不过所有过程中的已知解都留下来了)

  • 在 Phone letter combination 里也是一个道理，只不过这次我们不存过渡结果，只保留最后一层。

• insert 类

  • 比如 permutation ，这里解的构造方式靠 "insert"，所以 BFS 分层的搜索结构中，会反复出现靠插入构造出的新结果。

Subsets

这题三种解法的分析：

http://bangbingsyb.blogspot.com/2014/11/leetcode-subsets-i-ii.html

迭代：

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> rst = new ArrayList<>();
        rst.add(new ArrayList<Integer>());

        for(int i = 0; i < nums.length; i++){
            int n = rst.size();
            for(int j = 0; j < n; j++){
                List<Integer> list = new ArrayList<Integer>(rst.get(j));
                list.add(nums[i]);
                rst.add(list);
            }
        }

        return rst;
    }
}

位运算：

由于S[0: n-1]组成的每一个subset，可以看成是对是否包含S[i]的取舍。S[i]只有两种状态，包含在特定subset内，或不包含。所以subset的数量总共有2^n个。所以可以用0~2^n-1的二进制来表示一个subset。二进制中每个0/1表示该位置的S[i]是否包括在当前subset中。

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int totalAnswer = 1 << nums.length;
        List<List<Integer>> rst = new ArrayList<>(totalAnswer);

        for(int encoding = 0; encoding < totalAnswer; encoding++){
            List<Integer> curList = new ArrayList<>();
            for(int j = 0; j < nums.length; j++){
                if((encoding & (1 << j)) != 0) curList.add(nums[j]);
            }
            rst.add(curList);
        }

        return rst;
    }
}

Letter Combinations of a Phone Number

    public List<String> letterCombinations(String digits) {
        List<String> rst = new ArrayList<String>();
        if(digits == null || digits.length() == 0) return rst;
        String[] letters = new String[]{"", "", "abc", "def", "ghi", "jkl", 
                                        "mno", "pqrs", "tuv", "wxyz"};
        rst.add("");
        for(int i = 0; i < digits.length(); i++){
            int digit = digits.charAt(i) - '0';
            String next = letters[digit];
            int size = rst.size();
            List<String> nextLvl = new ArrayList<>();
            for(int j = 0; j < next.length(); j++){
                char chr = next.charAt(j);
                for(int k = 0; k < size; k++){
                    String newStr = rst.get(k) + chr;
                    nextLvl.add(newStr);
                }
            }
            rst = nextLvl;
        }
        return rst;
    }

Permutations

讨论帖子：

https://discuss.leetcode.com/topic/6377/my-ac-simple-iterative-java-python-solution

http://bangbingsyb.blogspot.com/2014/11/leetcode-permutations-i-ii.html

想迭代做这题，要先从理解为什么对于 cardinality = n 的集合，其总共的 permutation = n! 开始，permutation 的构造过程是：

• 第 n 层 permutation 的每个解中，有 n 个元素；

• 从n = 1 开始，放入第 1 个元素；

• 下一层要新加入的元素是 n + 1，在第 n + 1 层；

• 我们要从 n 层的所有结果中，插入所有可以插入的位置，对于每一个 size = n 的解，可插入位置为 n + 1 个；

• 于是每一层新得到的解的总数 F(n + 1) = F(n) * (n + 1), 可知 F(n) = n!

• 注意点1：一开始要加个 {} 进去，要么无法起始；

• 注意点2：List.add(index, ele) 记熟，不是 insert

• 注意点3: 插入范围要比 prevList.size() 大一个，所以具体有效的插入 index 是【0, prevList.size()】 的闭区间，

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> rst = new ArrayList<List<Integer>>();
        int n = nums.length;
        rst.add(new ArrayList<>());

        for(int i = 0; i < n; i++){
            int size = rst.size();
            List<List<Integer>> nextLvl = new ArrayList<List<Integer>>();
            for(int j = 0; j < size; j++){
                List<Integer> prevList = rst.get(j);
                for(int k = 0; k <= prevList.size(); k++){
                    List<Integer> curList = new ArrayList<Integer>(prevList);
                    curList.add(k, nums[i]);
                    nextLvl.add(curList);
                }
            }
            rst = nextLvl;
        }

        return rst;
    }