[Leetcode] String

Posted on | In , |

Introduction

Palindrome Problem

Manacher’s Algorithm

647. Palindromic Substrings

Leetcode: https://leetcode.com/problems/palindromic-substrings/

Expand from the center

1
2
3
4
5
6
7
8
9
10
11
def countSubstrings(self, s: str) -> int:
    n = 2 * len(s) - 1
    res = 0
    for i in range(n):
        left = i // 2
        right = (i + 1) // 2
        while left >= 0 and right <= len(s) - 1 and s[left] == s[right]:
            res += 1
            left -= 1
            right += 1
    return res

5. Longest Palindromic Substring

Leetcode: https://leetcode.com/problems/longest-palindromic-substring/

Solution 1: Expanding center