Posts tagged as “Palindrome”

花花酱 LeetCode 867. Prime Palindrome

By zxi on July 8, 2018

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)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int primePalindrome(int N) {

if (N <= 2) return 2;

if (N % 2 == 0) ++N;

while (true) {

if (reverse(N) == N && isPrime(N))

return N;

N += 2;

if (N > 11 & (int)log10(N) % 2 == 1)

// 13 -> 101

// 1001 -> 10001

N = pow(10, (int)log10(N) + 1) + 1;

}

return -1;

}

private:

int reverse(int n) {

int r = 0;

while (n) {

r = 10 * r + n % 10;

n /= 10;

}

return r;

}

bool isPrime(int n) {

if (n <= 1) return false;

for (int i = 2; i <= sqrt(n); ++i)

if (n % i == 0) return false;

return true;

}

};

花花酱 LeetCode 516. Longest Palindromic Subsequence

By zxi on May 28, 2018

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:

One possible longest palindromic subsequence is “bbbb”.

Example 2:
Input:

"cbbd"

Output:

One possible longest palindromic subsequence is “bb”.

Solution: DP

Time complexity: O(n^2)

Space complexity: O(n^2)

C++

// Author: Huahua

// Running time: 102 ms

class Solution {

public:

int longestPalindromeSubseq(string s) {

const int n = s.length();

vector<vector<int>> dp(n, vector<int>(n, 0));

for (int l = 1; l <= n; ++l)

for (int i = 0; i <= n - l; ++i) {

int j = i + l - 1;

if (i == j) {

dp[i][j] = 1;

continue;

}

dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

if (s[i] == s[j])

dp[i][j] = dp[i + 1][j - 1] + 2;

}

return dp[0][n - 1];

}

};

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 28 ms

class Solution {

public:

int longestPalindromeSubseq(string s) {

const int n = s.length();

vector<int> dp0(n); // sols of len = l

vector<int> dp1(n); // sols of len = l - 1

vector<int> dp2(n); // sols of len = l - 2

for (int l = 1; l <= n; ++l) {

for (int i = 0; i <= n - l; ++i) {

int j = i + l - 1;

if (i == j) {

dp0[i] = 1;

continue;

}

if (s[i] == s[j])

dp0[i] = dp2[i + 1] + 2;

else

dp0[i] = max(dp1[i + 1], dp1[i]);

}

dp0.swap(dp1);

dp2.swap(dp0);

}

return dp1[0];

}

};

Python3

"""

Author: Huahua

Running time: 1276 ms

"""

class Solution:

def longestPalindromeSubseq(self, s):

n = len(s)

dp0 = [0] * n

dp1 = [1] * n

dp2 = [0] * n

for l in range(2, n + 1):

for i in range(0, n - l + 1):

j = i + l - 1

if s[i] == s[j]:

dp0[i] = dp2[i + 1] + 2

else:

dp0[i] = max(dp1[i + 1], dp1[i])

dp0, dp1, dp2 = dp2, dp0, dp1

return dp1[0]

// Author: Huahua

// Running time: 116 ms (beats 100%)

public class Solution {

public int LongestPalindromeSubseq(string s) {

var n = s.Length;

var dp0 = new int[n];

var dp1 = new int[n];

var dp2 = new int[n];

for (var l = 1; l <= n; ++l) {

for (var i = 0; i <= n - l; ++i) {

int j = i + l - 1;

if (i == j) {

dp0[i] = 1;

continue;

}

if (s[i] == s[j])

dp0[i] = dp2[i + 1] + 2;

else

dp0[i] = Math.Max(dp1[i], dp1[i + 1]);

}

var tmp = dp2;

dp2 = dp1;

dp1 = dp0;

dp0 = tmp;

}

return dp1[0];

}

花花酱 LeetCode 647. Palindromic Substrings

By zxi on March 10, 2018

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:

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 1: Brute Force

Time complexity: O(n^2)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 5 ms

class Solution {

public:

int countSubstrings(string s) {

int ans = 0;

for (int i = 0; i < s.length(); ++i) {

ans += count(s, i, i); // odd length

ans += count(s, i, i + 1); // even length

}

return ans;

}

private:

int count(const string& s, int l, int r) {

int ans = 0;

while (l >= 0 & r < s.length() && s[l--] == s[r++])

++ans;

return ans;

}

};

花花酱 LeetCode 730. Count Different Palindromic Subsequences

By zxi on November 20, 2017

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:

Solution 1: Recursion with memoization

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

C++

// Author: Huahua

// Runtime: 72 ms

class Solution {

public:

int countPalindromicSubsequences(const string& S) {

const int n = S.length();

m_ = vector<vector<int>>(n + 1, vector<int>(n + 1, 0));

return count(S, 0, S.length() - 1);

}

private:

static constexpr long kMod = 1000000007;

long count(const string& S, int s, int e) {

if (s > e) return 0;

if (s == e) return 1;

if (m_[s][e] > 0) return m_[s][e];

long ans = 0;

if (S[s] == S[e]) {

int l = s + 1;

int r = e - 1;

while (l <= r && S[l] != S[s]) ++l;

while (l <= r && S[r] != S[s]) --r;

if (l > r)

ans = count(S, s + 1, e - 1) * 2 + 2;

else if (l == r)

ans = count(S, s + 1, e - 1) * 2 + 1;

else

ans = count(S, s + 1, e - 1) * 2

- count(S, l + 1, r - 1);

} else {

ans = count(S, s, e - 1)

+ count(S, s + 1, e)

- count(S, s + 1, e - 1);

}

return m_[s][e] = (ans + kMod) % kMod;

}

vector<vector<int>> m_;

};

Python

"""

Author: Huahua

Runtime: 3582 ms

"""

class Solution:

def countPalindromicSubsequences(self, S):

def count(S, i, j):

if i > j: return 0

if i == j: return 1

if self.m_[i][j]: return self.m_[i][j]

if S[i] == S[j]:

ans = count(S, i + 1, j - 1) * 2

l = i + 1

r = j - 1

while l <= r and S[l] != S[i]: l += 1

while l <= r and S[r] != S[i]: r -= 1

if l > r: ans += 2

elif l == r: ans += 1

else: ans -= count(S, l + 1, r - 1)

else:

ans = count(S, i + 1, j) + count(S, i, j - 1) - count(S, i + 1, j - 1)

self.m_[i][j] = ans % 1000000007

return self.m_[i][j]

n = len(S)

self.m_ = [[None for _ in range(n)] for _ in range(n)]

return count(S, 0, n - 1)

Java

// Author: Huahua

// Runtime: 107 ms

class Solution {

private int[][] m_;

private static final int kMod = 1000000007;

public int countPalindromicSubsequences(String S) {

int n = S.length();

m_ = new int[n][n];

return count(S.toCharArray(), 0, n - 1);

}

private int count(char[] s, int i, int j) {

if (i > j) return 0;

if (i == j) return 1;

if (m_[i][j] > 0) return m_[i][j];

long ans = 0;

if (s[i] == s[j]) {

ans += count(s, i + 1, j - 1) * 2;

int l = i + 1;

int r = j - 1;

while (l <= r && s[l] != s[i]) ++l;

while (l <= r && s[r] != s[i]) --r;

if (l > r) ans += 2;

else if (l == r) ans += 1;

else ans -= count(s, l + 1, r - 1);

} else {

ans = count(s, i, j - 1)

+ count(s, i + 1, j)

- count(s, i + 1, j - 1);

}

m_[i][j] = (int)((ans + kMod) % kMod);

return m_[i][j];

}

Solution 2: DP

C++

// Author: Huahua

// Runtime: 79 ms

class Solution {

public:

int countPalindromicSubsequences(const string& S) {

int n = S.length();

vector<vector<int>> dp(n, vector<int>(n, 0));

for (int i = 0; i < n; ++i)

dp[i][i] = 1;

for (int len = 1; len <= n; ++len) {

for (int i = 0; i < n - len; ++i) {

const int j = i + len;

if (S[i] == S[j]) {

dp[i][j] = dp[i + 1][j - 1] * 2;

int l = i + 1;

int r = j - 1;

while (l <= r && S[l] != S[i]) ++l;

while (l <= r && S[r] != S[i]) --r;

if (l == r) dp[i][j] += 1;

else if (l > r) dp[i][j] += 2;

else dp[i][j] -= dp[l + 1][r - 1];

} else {

dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];

}

dp[i][j] = (dp[i][j] + kMod) % kMod;

}

return dp[0][n - 1];

}

private:

static constexpr long kMod = 1000000007;

};

Pyhton

"""

Author: Huahua

Runtime: 3639 ms

"""

class Solution:

def countPalindromicSubsequences(self, S):

n = len(S)

if n == 0: return 0

dp = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n): dp[i][i] = 1

for size in range(2, n + 1):

for i in range(n - size + 1):

j = i + size - 1

if S[i] == S[j]:

dp[i][j] = dp[i + 1][j - 1] * 2

l = i + 1

r = j - 1

while l <= r and S[l] != S[i]: l += 1

while l <= r and S[r] != S[i]: r -= 1

if l > r: dp[i][j] += 2

elif l == r: dp[i][j] += 1

else: dp[i][j] -= dp[l + 1][r - 1]

else:

dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]

dp[i][j] %= 1000000007

return dp[0][n - 1]

Related Problems:

[解题报告] LeetCode 664. Strange Printer

Posts tagged as “Palindrome”

花花酱 LeetCode 867. Prime Palindrome

Problem

Solution: Math

花花酱 LeetCode 516. Longest Palindromic Subsequence

Problem

Solution: DP

花花酱 LeetCode 234. Palindrome Linked List

花花酱 LeetCode 647. Palindromic Substrings

花花酱 LeetCode 730. Count Different Palindromic Subsequences

Solution 1: Recursion with memoization

C++

Python

Java

Solution 2: DP

C++

Pyhton