陈中正的网络日志

LeetCode: Palindrome Partition

题目

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

分析

DFS来解决这个问题。

代码

class Solution
{
public:
    vector<vector<string>> partition(string s)
    {
        if (s.empty())
            return res;

        dfs(s, 0);

        return res;
    }

    void dfs(const string &s, int index)
    {
        if (index == s.size())
            res.push_back(solution);
        else
        {
            for (int i = index; i < s.size(); i++)
            {
                string substr = s.substr(index, i-index+1);
                if (isPalindrome(substr))
                {
                    solution.push_back(substr);
                    dfs(s, i+1);
                    solution.pop_back();
                }
            }
        }
    }

    bool isPalindrome(const string &s)
    {
        int left = 0;
        int right = s.size() - 1;

        while (left <= right)
        {
            if (s[left] != s[right])
                return false;
            left++;
            right--;
        }
        return true;
    }

    vector<vector<string>> res;
    vector<string> solution;
};

参考

http://fisherlei.blogspot.com/2013/03/leetcode-palindrome-partitioning.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39064961

Categories:  OJ题解 

« LeetCode: Reverse Words in a String LeetCode: Balanced Binary Tree »