LeetCode:647. Palindromic Substrings回文子串（C语言）

淩亂°似流年 2023-03-01 10:44 30阅读 0赞

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

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

示例 1:

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

示例 2:

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

注意:

输入的字符串长度不会超过1000。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/palindromic-substrings  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

int isPalindrome(char *buf, int left, int right){ 
        while(left < right){ 
            if(buf[left] == buf[right]){ 
                left++;
                right--;
            }
            else{ 
                return false;
            }
        }
        return true;
    }
    
    int countSubstrings(char * s){ 
        int len = strlen(s);
        int i,j;
        int count = 0;
    
        for(i = 0;i < len;i++){ 
            for(j = 0;i + j < len;j++){ 
                if(isPalindrome(s, i, i + j)){ 
                    count++;
                }
            }
        }
        return count;
    }

**运行结果：**  
![在这里插入图片描述][20200724111004379.png]

**Notes：**  
类似暴力法，但是第二层指针起点从字符串起始位置开始，第二层指针所指位置和第一层指针所指位置的长度的和要小于字符串总长度，在小于总长度的条件下判断第一层指针位置上的元素（right）与第二层指针位置上的元素（left）是否相等，若相等，left自减right自加，若最后left与right相等则表明是回文字符子串，返回true，否则不是，返回false。如此循环，直到遍历结束。

[20200724111004379.png]: /images/20230208/7d4bb89f0e07434daf0ef1407bc5a2fc.png