一、題目大意
給你一個字串 s ，請你統計并回傳這個字串中 回文子串 的數目，
回文字串 是正著讀和倒過來讀一樣的字串，
子字串 是字串中的由連續字符組成的一個序列，
具有不同開始位置或結束位置的子串，即使是由相同的字符組成，也會被視作不同的子串，
示例 1：
輸入：s = "abc"
輸出：3
解釋：三個回文子串: "a", "b", "c"
示例 2：
輸入：s = "aaa"
輸出：6
解釋：6個回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
- 1 <= s.length <= 1000
- s 由小寫英文字母組成
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/palindromic-substrings
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
二、解題思路
題意：給定一個字串，求其有多少個回文字串，回文的定義是左右對稱，輸入是一個字串，輸出一個整數，表示回文字串的數量，
我們可以從字串的每個位置開始，向左向右延長，判斷存在多少當前位置為中軸的回文字串，
三、解題方法
3.1 Java實作
public class Solution {
public int countSubstrings(String s) {
// 我們可以從字串的每個位置開始，向左向右延長，判斷存在多少以當前位置為中軸的回文 子字串，
int count = 0;
for (int i = 0; i < s.length(); i++) {
// 奇數長度
count += extendSubstrings(s, i, i);
// 偶數長度
count += extendSubstrings(s, i, i+1);
}
return count;
}
private int extendSubstrings(String s, int l, int r) {
int count = 0;
while (l >=0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
count++;
}
return count;
}
}
四、總結小記
- 2208/8/27 小孩子的哭聲讓人急的一身汗
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/502923.html
標籤：其他
上一篇：深入理解“字符編碼模型”