博客

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例 1:

输入: "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c".

示例 2:

输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".

解析：该题使用中心扩展方式，和

最长回文串

一样的思路。

class Solution {
public:
    int countSubstrings(string s) {
        if(s.size()<=1)
            return s.size();
        int count = 0;//回文串数目
        for(size_t i = 0;i<s.size();++i)
        {
            //处理奇数
            countSubstrings(s,i,i,count);
            //处理偶数
            countSubstrings(s,i,i+1,count);
        }
        return count;
    }
    void countSubstrings(string s,int left,int right,int &count)
    {
        while(left>=0 && right<s.size() && s[left] == s[right])
        {
            ++count;
            --left;
            ++right;
        }
    }
};

一条包含字母

A-Z

的消息通过以下方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个只包含数字的

非空

字符串，请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

题目整体思路就是dp，就是找当前位编码数和前一位编码数的关系以及前两位编码数的关系。 要分好几种情况来分析：

1. 如果当前位为0：
   • 如果前一位不是1或2，则这个0无法和任何数组成字母，代表整个串无法构成编码
   • 如果前一位是1或者2，则说明前一位和当前位能组成字母，这时候能构成的编码数目是和前前位相同的，即：
     
dp[i] = dp[i-2]

2. 如果当前位不为0：
   • 如果前一位和当前位能组成字母，则当前位的构成编码数目应该为前一位和前前位之和，即：
     
dp[i] = dp[i-1] + dp[i-2]

     ，当然要考虑当前位是否符合
     
i>=2?

   • 如果前一位和当前位不能组成字母，则当前位单独组成字母，即
     
dp[i] = dp[i-1]


这样就能解出所有情况下的状态转移方程，代码如下：

class Solution {
public:
    int numDecodings(string s) {
        if(s.empty() || s[0] == '0')
            return 0;
        vector<int> v(s.size());
        v[0] = 1;
        for(size_t i = 1;i<s.size();++i)
        {
            if(s[i] == '0')
            {
                if(s[i-1] != '1' && s[i-1] != '2')
                    return 0;
                if(s[i-1] == '1' || s[i-1] == '2')
                {
                    if(i>=2)
                        v[i] = v[i-2];
                    else //考虑i<1的情况
                        v[i] = 1;
                }
            }
            else
            {
                if(s[i-1] == '1' || (s[i-1] == '2' && s[i]<='6')){
                    v[i] = v[i-1] +1;
                    if(i>=2) //考虑i<1的情况
                        v[i] += (v[i-2] - 1);
                }
                else 
                    v[i] = v[i-1];
                
            }
        }
        return v[s.size()-1];
    }
};