資訊專欄INFORMATION COLUMN
Problem
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".
Note:
The input string length won"t exceed 1000.
土辦法，兩次循環(huán) O(n^3)
class Solution {
public int countSubstrings(String s) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = i+1; j <= s.length(); j++) {
String cur = s.substring(i, j);
if (isPalindrome(cur)) count++;
}
}
return count;
}
private boolean isPalindrome(String s) {
if (s.length() == 1) return true;
int i = 0, j = s.length()-1;
while (i <= j) {
if (s.charAt(i++) != s.charAt(j--)) return false;
}
return true;
}
}
中點(diǎn)延展法
class Solution {
int count = 0;
public int countSubstrings(String s) {
for (int i = 0; i < s.length(); i++) {
extendFromIndex(s, i, i);
extendFromIndex(s, i, i+1);
}
return count;
}
private void extendFromIndex(String s, int i, int j) {
while (i >= 0 && j < s.length() && s.charAt(i--) == s.charAt(j++)) {
count++;
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/77160.html
Problem Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0s and 1s, and all the 0s and all the 1s in these substrings are grouped consecutively. Subs...
摘要：則不算，因?yàn)閮蓚€(gè)被分割開(kāi)了，不是連續(xù)的。思路只記錄前一組是還是，以及出現(xiàn)的次數(shù)。相同，則判斷是否與前一個(gè)字符相同。那么此時(shí)需要拋棄前一組的所有內(nèi)容。當(dāng)前一組未配對(duì)字符數(shù)量達(dá)到時(shí)，說(shuō)明前一組已經(jīng)沒(méi)有可以匹配的字符。故把當(dāng)前組替換未前一組。 D88 696. Count Binary Substrings 題目鏈接 696. Count Binary Substrings 題目分析 給定一...
摘要：回文的意思就是反轉(zhuǎn)字符串后和原字符串相等。因?yàn)檫@種想法沒(méi)次都是兩邊同時(shí)擴(kuò)展。所以要分目標(biāo)字符串長(zhǎng)度為奇數(shù)目標(biāo)字符串為偶數(shù)兩種情況。 題目詳情 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.題目的意思是輸入...
摘要：難度題目是說(shuō)給出一個(gè)字符串求出這個(gè)字符串的最長(zhǎng)回文的子串回文是指前后完全對(duì)稱的字符串像是之類的都算是回文奇數(shù)字母的回文和偶數(shù)字母的回文中心是不一樣的奇數(shù)字母比如的中心在中間字母上偶數(shù)字母比如的回文在中間兩字母的中心上由此可見(jiàn)回文中心點(diǎn)實(shí)際上 Given a string s, find the longest palindromic substring in s. You may as...
摘要：題目解析題目是要找出最長(zhǎng)的回文字符串，拿到題目的第一反應(yīng)是遍歷子串，然后一直替換最長(zhǎng)的子字符串即可了。但是這種解法遇到極端輸入狀況就會(huì)超時(shí)，指定的最長(zhǎng)長(zhǎng)度為，遍歷子串需要兩次循環(huán)，判斷回文需要一次循環(huán)，所以總的效率為，那么極端狀況會(huì)超時(shí)。 題目 Given a string s, find the longest palindromic substring in s. You may ...
閱讀 3212·2021-11-08 13:18
閱讀 1366·2021-10-09 09:57
閱讀 1197·2021-09-22 15:33
閱讀 3997·2021-08-17 10:12
閱讀 5079·2021-08-16 11:02
閱讀 2693·2019-08-30 10:56
閱讀 975·2019-08-29 18:31
閱讀 3263·2019-08-29 16:30
