LeetCode 140 Word Break II

    
        标签：
        
            回溯法
        
            LeetCode
        
    发布于：2022-03-02 16:46:25
    编辑于：2022-03-02 16:52:30
    浏览量：700

概述

https://leetcode.com/problems/word-break-ii/

这是一道 Hard 题。

回溯法

其实是有重复的子问题的，懒得加 cache 了。

class Solution {
public:
    set<string> c;
    vector<string> ans;
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        for (auto& w : wordDict) c.insert(w);
        vector<string> path = {};
        helper(s, 0, path);
        return ans;
    }
    
    void helper(string& s, int k, vector<string>& path) {
        if (k == s.size()) {
            string res;
            for (int i = 0; i < path.size(); i ++) {
                res += path[i];
                if (i != path.size() - 1) res += " ";
            }
            ans.push_back(res);
            return;
        }
        string t;
        for (int i = k; i < s.size(); i ++) {
            t += s[i];
            if (c.count(t) != 0) {
                path.push_back(t);
                helper(s, i + 1, path);
                path.pop_back();
            }
        }
    }
};

Links: leetcode-140-word-break-ii