Press "Enter" to skip to content

Posts tagged as “Palindrome”

花花酱 LeetCode 9. Palindrome Number

Problem

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Could you solve it without converting the integer to a string?

Solution 1: Convert to string (cheating)

Time complexity: O(log10(x))

Space complexity: O(log10(x))

C++

Solution 2: Digit by Digit

Every time we compare the first and last digits of x, if they are not the same, return false. Otherwise, remove first and last digit and continue this process.

How can we achieve that via int math?

e.g. x = 9999, t = pow((10, int)log10(x)) = 1000

first digit: x / t, last digit: x % 10

then x = (x – x / t * t) / 10 removes first and last digits.

t /= 100 since we removed two digits.

x / t = 9 = 9 = x % 10, 9999 => 99

9 = 9, 99 => “”

Time complexity: O(log10(x) / 2)

Space complexity: O(1)

C++

花花酱 LeetCode 5. Longest Palindromic Substring

Problem

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

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

Solution: Greedy

Try all possible i and find the longest palindromic string whose center is i (odd case) and i / i + 1 (even case).

Time complexity: O(n^2)

Space complexity: O(1)

C++

Python3

花花酱 LeetCode 867. Prime Palindrome

Problem

Find the smallest prime palindrome greater than or equal to N.

Recall that a number is prime if it’s only divisors are 1 and itself, and it is greater than 1.

For example, 2,3,5,7,11 and 13 are primes.

Recall that a number is a palindrome if it reads the same from left to right as it does from right to left.

For example, 12321 is a palindrome.

 

Example 1:

Input: 6
Output: 7

Example 2:

Input: 8
Output: 11

Example 3:

Input: 13
Output: 101

Note:

  • 1 <= N <= 10^8
  • The answer is guaranteed to exist and be less than 2 * 10^8.

Solution: Math

All odd digits palindromes have a factor 11, they are not prime except 11 itself.

Time complexity: O(n)

Space complexity: O(1)

 

花花酱 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++