Re: [閒聊] 每日leetcode

[ray90514 ()]

140. Word Break II
改寫之前寫過的 Word Break I
舉例wordDict = aba ba ab a
ababa從結尾拆可以是(ab)aba (aba)ba (abba)a
括號裡面可以繼續拆

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        vector<vector<string>> dp(s.size() + 1);
        dp[0] = {""};
        for(int i = 1; i <= s.size(); i++){
            for(auto word : wordDict){
                int len = word.size();
                if(i - len >= 0 && s.compare(i - len, len, word) == 0){
                    for(string s : dp[i - len]){
                        if(s != "")
                            s += ' ';
                        dp[i].push_back(s + word);
                    }

                };
            }
        }
        return dp.back();
    }
};

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.36.41.116 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716597737.A.55F.html
※ 編輯: ray90514 (114.36.41.116 臺灣), 05/25/2024 08:43:01