Java&C++题解与拓展——leetcode691.贴纸拼词【么的新知识】

• 题目要求
• 思路：DFS+记忆化搜索
• • Java
  • C++
• 总结

• 用一个二进制串 s t a t e state state的每一位表示当前字母是否被拼出， 1 1 1为拼出；
  • 初始 s t a t e state state为 0 0 0，拼成后 s t a t e state state为 ( 1 < < n ) − 1 (1<
• 每个贴纸都可以多次使用，所以从某一状态到最终结果的最小步数是固定的，所以定义一个 f f f数组记录每个 s t a t e state state的结果，避免重复搜索（记忆化搜索）；
  • 用枚举 s t i c k e r s stickers stickers的方式更新 s t a t e state state，下一状态为 n s ns ns，则 f [ s t a t e ] f[state] f[state]的值为最小的 d f s ( n s ) + 1 dfs(ns)+1 dfs(ns)+1，即下一状态到结果的最小步数。

class Solution {
    int N = 20, M = 1 << 20, INF = 50;
    int[] f = new int[M]; // 记录已搜索状态结果
    String[] stickers;
    String target;
    int n;
    int dfs(int state) { // 用二进制数表示每一位状态
        if(state == ((1 << n) - 1)) // 全1即已拼成
            return 0;
        if(f[state] != -1) // 查询当前状态是否计算过
            return f[state];
        int res = INF;
        for(String s : stickers) {
            int ns = state; // 下一状态
            for(char c : s.toCharArray()) { // 逐位比较
                for(int i = 0; i < n; i++) {
                    if(target.charAt(i) == c && ((ns >> i) & 1) == 0) { // 可贴且未遍历
                        // 当前位状态置1
                        ns |= (1 << i);
                        break; // 跳出循环下一位
                    }
                }
            }
            if(ns != state) // 以下一状态继续搜索
                res = Math.min(res, dfs(ns) + 1);
        }
        return f[state] = res;
    }

    public int minStickers(String[] stickers, String target) {
        this.stickers = stickers;
        this.target = target;
        n = target.length();
        Arrays.fill(f, -1);
        int res = dfs(0);
        return res == INF ? -1 : res;
    }
}

• 时间复杂度： O ( 2 n × ∑ i = 0 m − 1 s t i c k e r s [ i ] . l e n g t h × n ) O(2^ntimessum^{m-1}_{i=0}stickers[i].lengthtimes n) O(2n×∑i=0m−1​stickers[i].length×n)，其中 n n n为字符串 t a r g e t target target的长度， m m m为数组 s t i c k e r s stickers stickers的长度，可知共有 2 n 2^n 2n个状态，每个状态都要遍历数组和字符串，计算复杂度为 O ( ∑ i = 0 m − 1 s t i c k e r s [ i ] . l e n g t h × n ) O(sum^{m-1}_{i=0}stickers[i].lengthtimes n) O(∑i=0m−1​stickers[i].length×n)。
• 空间复杂度： O ( 2 n ) O(2^n) O(2n)

const static int N = 20, M = 1 << 20, INF = 50;
class Solution {
    int n;
    int f[M]; // 记录已搜索状态结果
    vector stickers;
    string target;
public:
    int minStickers(vector& stickers, string target) {
        this->stickers = stickers;
        this->target = target;
        n = target.size();
        memset(f, -1, M);
        int res = dfs(0);
        return res == INF ? -1 : res;
    }

    int dfs(int state) { // 用二进制数表示每一位状态
        if(state == ((1 << n) - 1)) // 全1即已拼成
            return 0;
        if(f[state] != -1) // 查询当前状态是否计算过
            return f[state];
        int res = INF;
        for(auto s : stickers) {
            int ns = state; // 下一状态
            for(auto c : s) { // 逐位比较
                for(int i = 0; i < n; i++) {
                    if(target[i] == c && ((ns >> i) & 1) == 0) { // 可贴且未遍历
                        // 当前位状态置1
                        ns |= (1 << i);
                        break; // 跳出循环下一位
                    }
                }
            }
            if(ns != state) // 以下一状态继续搜索
                res = min(res, dfs(ns) + 1);
        }
        return f[state] = res;
        
    }
};

• 时间复杂度： O ( 2 n × ∑ i = 0 m − 1 s t i c k e r s [ i ] . l e n g t h × n ) O(2^ntimessum^{m-1}_{i=0}stickers[i].lengthtimes n) O(2n×∑i=0m−1​stickers[i].length×n)，其中 n n n为字符串 t a r g e t target target的长度， m m m为数组 s t i c k e r s stickers stickers的长度，可知共有 2 n 2^n 2n个状态，每个状态都要遍历数组和字符串，计算复杂度为 O ( ∑ i = 0 m − 1 s t i c k e r s [ i ] . l e n g t h × n ) O(sum^{m-1}_{i=0}stickers[i].lengthtimes n) O(∑i=0m−1​stickers[i].length×n)。
• 空间复杂度： O ( 2 n ) O(2^n) O(2n)

感觉不是很好理解，看了半天也没有完全懂，带着实例推导了几轮才理清楚一点，其实就是排列组合的枚举，然后记录状态。

DFS就是以每个贴纸单词为基础深入到拼成状态，然后再换下一个贴纸……