转载

palindrome-partitioning

palindrome-partitioning

题目描述

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s =”aab”,
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

思路

暴力的dfs

class Solution {
public:
    vector<vector<string>> partition(string s) {
       vector<string> item;
       vector<vector<string>> res;
       if(s.size() == 0) return res;
       dfs(s, 0, item, res);
       return res;
    }

    void dfs(string s, int index, vector<string> item, vector<vector<string>> &res) {
        if(index >= s.size()) {
            res.push_back(item);
            return;
        }
        for(int i = index; i < s.size(); i++) {
            if(palindrome(s.substr(index, i-index + 1))) {
                item.push_back(s.substr(index, i-index + 1));
                dfs(s, i+1, item, res);
                item.pop_back();
            }
        }
    }
    /*判断回文*/
    bool palindrome(string s){
       int len = s.size();
       for(int i = 0; i < len / 2; i++) {
           if(s[i] != s[len - i -1]) return false;
       }
       return true;
    }
};
正文到此结束
本文目录