Palindromic Substrings
给一个字符串, 找到所有可能的回文子字符串的个数.
这题还是很巧妙的, 利用回文的性质, 就是奇数对称和偶数对称两种回文, 然后搜索, couting一下即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Solution { public int countSubstrings(String s) { int n = s.length(); int res = 0; for(int i = 0; i < n; i++) { int odd = count(s, i, i); int even = count(s,i, i + 1); res += odd; res += even; } return res; } private int count(String s, int start, int end){ int i = start; int j = end; int res = 0; while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)){ res++; i--; j++; } return res; } //abbacca } |