647. Palindromic Substrings

LeetCode medium original: C# #csharp #leetcode #medium #string #tree #two-pointers

選択した UI 言語に合わせて問題文をロシア語から翻訳します。コードは変更しません。

LeetCode Static

Если задана 文字列 s, return количество палиндромных подстрок в ней. 文字列 является палиндромом, если она читается так же, как задом наперед. substring - это непрерывная последовательность символов в строке.

例:

Input: s = "abc"

Output: 3

C# 解法

照合済み/オリジナル

public class Solution {
    public int CountSubstrings(string s) {
        int totalCount = 0;
        for (int i = 0; i < s.Length; i++) {
            totalCount += ExpandAroundCenter(s, i, i);
            totalCount += ExpandAroundCenter(s, i, i + 1);
        }
        return totalCount;
    }
    private int ExpandAroundCenter(string s, int left, int right) {
        int count = 0;
        while (left >= 0 && right < s.Length && s[left] == s[right]) {
            count++;
            left--;
            right++;
        }
        return count;
    }
}

C++ 解法

自動ドラフト、提出前に確認

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int CountSubstrings(string s) {
        int totalCount = 0;
        for (int i = 0; i < s.size(); i++) {
            totalCount += ExpandAroundCenter(s, i, i);
            totalCount += ExpandAroundCenter(s, i, i + 1);
        }
        return totalCount;
    }
    private int ExpandAroundCenter(string s, int left, int right) {
        int count = 0;
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            count++;
            left--;
            right++;
        }
        return count;
    }
}

Java 解法

照合済み/オリジナル

public class Solution {
    public int countSubstrings(String s) {
        int totalCount = 0;
        for (int i = 0; i < s.length(); i++) {
            totalCount += expandAroundCenter(s, i, i);
            totalCount += expandAroundCenter(s, i, i + 1);
        }
        return totalCount;
    }

    private int expandAroundCenter(String s, int left, int right) {
        int count = 0;
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            count++;
            left--;
            right++;
        }
        return count;
    }
}

JavaScript 解法

照合済み/オリジナル

var countSubstrings = function(s) {
    const expandAroundCenter = (left, right) => {
        let count = 0;
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            count++;
            left--;
            right++;
        }
        return count;
    };

    let totalCount = 0;
    for (let i = 0; i < s.length; i++) {
        totalCount += expandAroundCenter(i, i);
        totalCount += expandAroundCenter(i, i + 1);
    }
    return totalCount;
};

Python 解法

照合済み/オリジナル

def countSubstrings(s):
    def expandAroundCenter(left, right):
        count = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
        return count
    
    total_count = 0
    for i in range(len(s)):
        total_count += expandAroundCenter(i, i)  # For odd length palindromes
        total_count += expandAroundCenter(i, i + 1)  # For even length palindromes
    return total_count

Go 解法

照合済み/オリジナル

package main

func expandAroundCenter(s string, left, right int) int {
    count := 0
    for left >= 0 && right < len(s) && s[left] == s[right] {
        count++
        left--
        right++
    }
    return count
}

func countSubstrings(s string) int {
    totalCount := 0
    for i := 0; i < len(s); i++ {
        totalCount += expandAroundCenter(s, i, i)
        totalCount += expandAroundCenter(s, i, i+1)
    }
    return totalCount
}

Algorithm

Инициализируйте счетчик для подсчета палиндромных подстрок.

Для каждой позиции в строке используйте два метода расширения: один для палиндромов нечетной длины и один для палиндромов четной длины.

Расширяйте от центра, проверяя, является ли substring палиндромом, и увеличивайте счетчик, если 問題文 выполняется.

😎

Vacancies for this task

有効な求人 with overlapping task tags are 表示.

すべての求人

有効な求人はまだありません。