Press "Enter" to skip to content

Posts tagged as “Palindrome”

花花酱 LeetCode 516. Longest Palindromic Subsequence

Problem

题目大意:找出最长回文子序列的长度。

https://leetcode.com/problems/longest-palindromic-subsequence/description/

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

"bbbab"

Output:

4

One possible longest palindromic subsequence is “bbbb”.

Example 2:
Input:

"cbbd"

Output:

2

One possible longest palindromic subsequence is “bb”.

Solution: DP

Time complexity: O(n^2)

Space complexity: O(n^2)

C++

Time complexity: O(n^2)

Space complexity: O(n)

C++

Python3

C#

 

花花酱 LeetCode 234. Palindrome Linked List

题目大意:检查一个单向链表是不是回文。

Problem:

https://leetcode.com/problems/palindrome-linked-list/description/

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

Idea:

  1. use fast / slow pointers to find the middle node and see whether the list has odd/even number of elements.
  2. Reverse the right half the list, and compare with the left half

E.g.
1->2->3->4->3->2->1->null
fast = null
slow = 4
slow->next = 3
reverse(slow->next)
null<-3<-2<-1 compare with 1->2->3->…

Solution: 1

Time complexity: O(n)

Space complexity: O(1)

C++

 

 

 

花花酱 LeetCode 647. Palindromic Substrings

Problem:

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

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:

Example 2:

Note:

  1. The input string length won’t exceed 1000.

Solution 1: Brute Force

Time complexity: O(n^2)

Space complexity: O(1)

C++

 

花花酱 LeetCode 730. Count Different Palindromic Subsequences

Problem:

Given a string S, find the number of different non-empty palindromic subsequences in S, and return that number modulo 10^9 + 7.

A subsequence of a string S is obtained by deleting 0 or more characters from S.

A sequence is palindromic if it is equal to the sequence reversed.

Two sequences A_1, A_2, ... and B_1, B_2, ... are different if there is some i for which A_i != B_i.

Example 1:

Input: 
S = 'bccb'
Output: 6
Explanation: 
The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'.
Note that 'bcb' is counted only once, even though it occurs twice.

Example 2:

Input: 
S = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
Output: 104860361
Explanation: 
There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 10^9 + 7.

Note:

 

  • The length of S will be in the range [1, 1000].
  • Each character S[i] will be in the set {'a', 'b', 'c', 'd'}.



Idea:

DP

 

Solution 1: Recursion with memoization

Time complexity: O(n^2)
Space complexity: O(n^2)

C++

Python

Java

Solution 2: DP

C++

Pyhton

Related Problems:

花花酱 LeetCode 680. Valid Palindrome II

Problem:

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Example 2:

Note:

  1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

Idea:

Greedy, delete the first unmatched char



Time complexity

O(n)

Solution: