647. Palindromic Substrings

题目描述：

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c".

 

Example 2:

Input: "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

解题思路：

本体主要是考察s中每个子字符串是否是回文字符串，有两种方法：

1.是确定子字符串的首尾，判断是否为回文字符串。

2.以每个字符为中心，向两端延伸判断是否相等，相等时回文字符串个数加一，不相等时终止内层循环。

相比较而言，第二种方法效率更高，可以更快终止遍历。

代码：

1 class Solution { 2 public: 3 int countSubstrings(string s) { 4 int ret = s.size(); 5 int j; 6 for (int i = 0; i < s.size(); i++){ 7 for (int j = i + 1; j < s.size(); ++j) { 8 if (s[i] != s[j]) 9 continue; 10 else 11 if (check(s, i, j)) 12 ret++; 13 } 14 } 15 return ret; 16 } 17 bool check(const string& s, int left, int right) { 18 int i = left; 19 int j = right; 20 for(;i <= j; i++, j--) { 21 if (s[i] != s[j]) 22 return false; 23 } 24 return true; 25 } 26 }; View Code 1 class Solution { 2 public: 3 int countSubstrings(string s) { 4 int ret = 0; 5 for (int i = 0; i < s.size(); i++) { 6 ret += check(s, i, i); 7 ret += check(s, i, i+1); 8 } 9 return ret; 10 } 11 int check(const string& s, int left, int right) { 12 int num = 0; 13 while (left>=0 && right<s.size() && s[left--]==s[right++]) 14 num++; 15 return num; 16 } 17 }; View Code

 

class Solution {public:    int countSubstrings(string s) {        int ret = 0;        for (int i = 0; i < s.size(); i++) {            ret += check(s, i, i);            ret += check(s, i, i+1);        }        return ret;    }    int check(const string& s, int left, int right) {        int num = 0;        while (left>=0 && right<s.size() && s[left--]==s[right++])            num++;        return num;    }};

转载于:https://www.cnblogs.com/gsz-/p/9538491.html

与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的647. Palindromic Substrings的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。