[LeetCode] 1771. Maximize Palindrome Length From Subsequences

轉自LeetCode

You are given two strings, word1 and word2. You want to construct a string in the following manner:

• Choose some non-empty subsequence subsequence1 from word1.
• Choose some non-empty subsequence subsequence2 from word2.
• Concatenate the subsequences: subsequence1 + subsequence2, to make the string.

Return the length of the longest palindrome that can be constructed in the described manner. If no palindromes can be constructed, return 0.

A subsequence of a string s is a string that can be made by deleting some (possibly none) characters from s without changing the order of the remaining characters.

A palindrome is a string that reads the same forward as well as backward.

 

Example 1:

Input: word1 = "cacb", word2 = "cbba"
Output: 5
Explanation: Choose "ab" from word1 and "cba" from word2 to make "abcba", which is a palindrome.

Example 2:

Input: word1 = "ab", word2 = "ab"
Output: 3
Explanation: Choose "ab" from word1 and "a" from word2 to make "aba", which is a palindrome.

Example 3:

Input: word1 = "aa", word2 = "bb"
Output: 0
Explanation: You cannot construct a palindrome from the described method, so return 0.

 

Constraints:

• 1 <= word1.length, word2.length <= 1000
• word1 and word2 consist of lowercase English letters.

Solution

516. Longest Palindromic Subsequence 的衍生題

這次是要從兩個 string 來組成最長的 palindromic subsequence

而且還規定，一定必須從兩個 string 中各取一個 subsequence 出來

不能有 empty subsequence

整體解法和 516 題一樣

首先，將兩個 string 串起來，word = word1 + word2

然後用 516 的解法，在 word 裡找到最長的 palindromic subsequence

然後因為 word 是由 word1 和 word2 串起來的，又要確保兩邊都有用到

所以在過程中，如果 left < word1.length && right >= word1.length 的時候

就符合題意，兩邊都有取到值，這時候紀錄符合條件的最大值

最後就可以找到答案

kotlin(參考解法)

	class Solution {
	fun longestPalindrome(word1: String, word2: String): Int {
	val word = word1 + word2
	val dp = Array(word.length) { IntArray(word.length) {0} }
	var ans = 0
	for(left in word.lastIndex downTo 0) {
	dp[left][left] = 1
	for(right in left+1 until word.length) {
	if(word[left] == word[right]) {
	dp[left][right] = dp[left+1][right-1] + 2
	if(left < word1.length && right >= word1.length) {
	ans = Math.max(ans, dp[left][right])
	}
	} else {
	dp[left][right] = Math.max(dp[left+1][right], dp[left][right-1])
	}
	}
	}
	return ans
	}
	}

view raw maximize_palindrome_length_from_subsequences.kt hosted with ❤ by GitHub