1616. Split Two Strings to Make Palindrome
You are given two strings a
and b
of the same length. Choose an index and split both strings at the same index, splitting a
into two strings: aprefix
and asuffix
where a = aprefix + asuffix
, and splitting b
into two strings: bprefix
and bsuffix
where b = bprefix + bsuffix
. Check if aprefix + bsuffix
or bprefix + asuffix
forms a palindrome.
When you split a string s
into sprefix
and ssuffix
, either ssuffix
or sprefix
is allowed to be empty. For example, if s = "abc"
, then "" + "abc"
, "a" + "bc"
, "ab" + "c"
, and "abc" + ""
are valid splits.
Return true
if it is possible to form a palindrome string, otherwise return false
.
Notice that x + y
denotes the concatenation of strings x
and y
.
Example 1:
Input: a = "x", b = "y" Output: true Explaination: If either a or b are palindromes the answer is true since you can split in the following way: aprefix = "", asuffix = "x" bprefix = "", bsuffix = "y" Then, aprefix + bsuffix = "" + "y" = "y", which is a palindrome.
Example 2:
Input: a = "abdef", b = "fecab" Output: true
Example 3:
Input: a = "ulacfd", b = "jizalu" Output: true Explaination: Split them at index 3: aprefix = "ula", asuffix = "cfd" bprefix = "jiz", bsuffix = "alu" Then, aprefix + bsuffix = "ula" + "alu" = "ulaalu", which is a palindrome.
Example 4:
Input: a = "xbdef", b = "xecab" Output: false
Constraints:
1 <= a.length, b.length <= 105
a.length == b.length
a
andb
consist of lowercase English letters
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | class Solution { public boolean checkPalindromeFormation(String a, String b) { if(helper(a, b, 0, b.length()-1, false)) return true; return helper(b, a, 0, a.length()-1, false); } boolean helper(String a, String b, int l, int r, boolean oneString){ if(l>=r) return true; if(a.charAt(l)!=b.charAt(r)) return false; if(helper(a, b, l+1, r-1, oneString)) return true; if(!oneString){ if(helper(a, a, l+1, r-1, true)) return true; if(helper(b, b, l+1, r-1, true)) return true; } return false; } } |
No comments:
Post a Comment