[LeetCode] 647. Palindromic Substrings

鄒立鵬發布于2019-08-19 11:11 / 2662人閱讀

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.

Solution

土辦法，兩次循環 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;
    }
}

中點延展法

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++;
        }
    }
}

云服務器 GPU云服務器 Palindromic Substrings LeetCode LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/77160.html

[LintCode/LeetCode] Count Binary Substrings

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...

BaronZhang 2019-08-16 12:44 評論0 收藏0
Leetcode PHP題解--D88 696. Count Binary Substrings

摘要：則不算，因為兩個被分割開了，不是連續的。思路只記錄前一組是還是，以及出現的次數。相同，則判斷是否與前一個字符相同。那么此時需要拋棄前一組的所有內容。當前一組未配對字符數量達到時，說明前一組已經沒有可以匹配的字符。故把當前組替換未前一組。 D88 696. Count Binary Substrings 題目鏈接 696. Count Binary Substrings 題目分析給定一...

lanffy 2019-07-01 14:00 評論0 收藏0
leetcode 5 Longest Palindromic Substring Java &

摘要：回文的意思就是反轉字符串后和原字符串相等。因為這種想法沒次都是兩邊同時擴展。所以要分目標字符串長度為奇數目標字符串為偶數兩種情況。題目詳情 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.題目的意思是輸入...

JessYanCoding 2019-08-15 14:27 評論0 收藏0
Leetcode 5 Longest Palindromic Substring 最長回文子串

摘要：難度題目是說給出一個字符串求出這個字符串的最長回文的子串回文是指前后完全對稱的字符串像是之類的都算是回文奇數字母的回文和偶數字母的回文中心是不一樣的奇數字母比如的中心在中間字母上偶數字母比如的回文在中間兩字母的中心上由此可見回文中心點實際上 Given a string s, find the longest palindromic substring in s. You may as...

NotFound 2019-08-14 17:12 評論0 收藏0
LeetCode-5 Longest Palindromic Substring

摘要：題目解析題目是要找出最長的回文字符串，拿到題目的第一反應是遍歷子串，然后一直替換最長的子字符串即可了。但是這種解法遇到極端輸入狀況就會超時，指定的最長長度為，遍歷子串需要兩次循環，判斷回文需要一次循環，所以總的效率為，那么極端狀況會超時。題目 Given a string s, find the longest palindromic substring in s. You may ...

psychola 2019-08-16 13:53 評論0 收藏0