string切割问题求解

字符串切割问题求解

我在做Leetecode的一道题时，遇到了一道切割字符串求解回文字符串的题目，题目大意如下:

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算法，进行深搜，但是这个里我们需要注意的一个问题是，每个字符只能用一次，而且不能使用拼接的方式，需要直接从string s中截取子字符串，所以我们使用s.substr(start,count)的方式。这个不同于之前的combinationSum的题目，需要有一个中间target保存。我们只需要传入下面几个参数即可，使用step来标示当前指向s的开头index，i为结束index。

void DFS(....){
        if(step>=s.size()){
            result.push_back(path);
            return;
        }
        for(auto i = step;i 小于 s.size();i++){
            if(is_palindrome(s,step,i)){
                path.push_back(s.substr(step,i-step+1));
                DFS(s,result,path,i+1);
                path.pop_back();
            }
        }
    }
 
    bool is_palindrome(string &s,int start,int end){
        while(start 小于 end){
            if(s[start]!=s[end])
                return false;
            start++;
            end--;
        }
        return true;
    }
};

一个长度为n 的字符串，有n-1 个地方可以砍断，每个地方可断可不断，因此复杂度为O(2^(n-1))

https://leetcode.com/problems/palindrome-partitioning/