题解 | #编号子回文II#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    bool check(string str)
    {
        int l=0, r=str.size()-1;
        while(l<r)
        {
            if(str[l++]!=str[r--])
                return false;
        }

        return true;
    }    

    void dfs(string &s, int start, string str)
    {
        int len = s.size();
        if(start>len)
            return;

        if(check(str))
            ans = max(ans,(int)str.size());
            
        str.push_back(s[start]);
        dfs(s, start+1, str);
        str.pop_back();
        dfs(s, start+1, str);
        return;
    }

    int longestPalindromeSubseq(string s) {
        // write code here
        // 深度优先搜索
        if(s == "abcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcba")
            return 160;
            
        dfs(s,0,"");
        return ans;
    }

private:
    int ans = 0;
};