美文网首页
131. Palindrome Partitioning

131. Palindrome Partitioning

作者: 刘小小gogo | 来源:发表于2018-08-26 10:25 被阅读0次
    image.png

    类似于subset

    class Solution {
    public:
        vector<vector<string>> partition(string s) {
            vector<vector<string>> result;
            vector<string> list;
            if(s.empty()) return result;
            dfs(0, result, list, s);
            return result;
        }
    private:
        void dfs(int pos, vector<vector<string>>& result, vector<string>& list, string s){
            if(pos == s.size()){
                result.push_back(list);
            }
            for(int i = pos; i < s.size(); i++){//
                string substr = s.substr(pos, i + 1 - pos);
                if(!isPalindrome(substr)) continue;
                list.push_back(substr);
                dfs(i+1, result, list, s);//因为这种类似于拼接的题目,subset之类的,取过的不能取, 只能往后取了,所以要是i+1
                list.pop_back();
            }
        }
        bool isPalindrome(string str){
            if(str.empty()) return false;
            int l = 0, r = str.size() - 1;
            while(l <= r){
                if(str[l] != str[r]){
                    return false;
                }
                l++;
                r--;
            }
            return true;
        }
    };
    

    相关文章

      网友评论

          本文标题:131. Palindrome Partitioning

          本文链接:https://www.haomeiwen.com/subject/iqzniftx.html