[每日一题]1616.分割两个字符串得到回文串
1616. 分割两个字符串得到回文串 给你两个字符串 a 和 b ，它们长度相同。请你选择一个下标，将两个字符串都在 相同的下标 分割开。由 a 可以得到两个字符串： a prefix 和 a suffix ，满足 a = a prefix + a suffix ，同理，由 b 可以得到两个字符串 b prefix 和 b suffix ，满足 b = b prefix + b suffix 。请你判断 a prefix + b suffix 或者 b prefix + a suffix 能否构成回文串。
当你将一个字符串 s 分割成 sprefix 和 ssuffix 时， ssuffix 或者 sprefix 可以为空。比方说， s = “abc” 那么 “” + “abc” ， “a” + “bc” ， “ab” + “c” 和 “abc” + “” 都是合法分割。
如果 能构成回文字符串 ，那么请返回 true，否则返回 false 。
注意， x + y 表示连接字符串 x 和 y 。
输入：a = “x”, b = “y” 输出：true 解释：如果 a 或者 b 是回文串，那么答案一定为 true ，因为你可以如下分割： aprefix = “”, asuffix = “x” bprefix = “”, bsuffix = “y” 那么 aprefix + bsuffix = “” + “y” = “y” 是回文串。
输入：a = “ulacfd”, b = “jizalu” 输出：true 解释：在下标为 3 处分割： aprefix = “ula”, asuffix = “cfd” bprefix = “jiz”, bsuffix = “alu” 那么 aprefix + bsuffix = “ula” + “alu” = “ulaalu” 是回文串。
提示：
- 1 <= a.length, b.length <= 105
- a.length == b.length
- a 和 b 都只包含小写英文字母
Solutions
class Solution {
public boolean checkPalindromeFormation(String a, String b) {
String a_ = new StringBuilder(a).reverse().toString();
String b_ = new StringBuilder(b).reverse().toString();
return checkPalindromeFormation_(a,b) || checkPalindromeFormation_(b,a)
|| checkPalindromeFormation_(a_,b_) || checkPalindromeFormation_(b_,a_);
}
private boolean checkPalindromeFormation_(String a,String b){
int left = 0 , right = a.length()-1;
while(left < right){
if(a.charAt(left) != b.charAt(right)){
if(b != a){
b = a;
continue;
}
return false;
}
left++;
right--;
}
return true;
}
}
class Solution {
public boolean checkPalindromeFormation(String a, String b) {
return checkConcatenation(a, b) || checkConcatenation(b, a);
}
public boolean checkConcatenation(String a, String b) {
int n = a.length();
int left = 0, right = n - 1;
while (left < right && a.charAt(left) == b.charAt(right)) {
left++;
right--;
}
if (left >= right) {
return true;
}
return checkSelfPalindrome(a, left, right) || checkSelfPalindrome(b, left, right);
}
public boolean checkSelfPalindrome(String a, int left, int right) {
while (left < right && a.charAt(left) == a.charAt(right)) {
left++;
right--;
}
return left >= right;
}
}
Ideas
-
双指针
记字符串的长度为 n，分割的下标为 k，即下标 k 之前的字符构成前缀，下标 k 和之后的字符构成后缀，前缀长度为 k，后缀长度为 n−k，0≤k≤n。
接下来需要判断
a prefix +b suffix或者b prefix+a suffix能否构成回文字符串，首先判断a prefix+b suffix能否构成回文字符串。这个字符串的起始位置是由 a 组成的，末尾位置是由 b 构成的。要想构成回文，起始的部分和末尾的部分必须是倒序相等的，这个可以用双指针来逐位判断。当遇到不相等的情况时，则说明遇到了分割点，分割的位置可能是左侧的指针，也可能是右侧的指针。如果分割点是左侧的指针，则需要 b 在双指针之间的字符串构成回文；如果分割点是右侧的指针，则需要 a 在双指针之间的字符串构成回文。这二者满足其一即可。判断
b prefix +a suffix能否构成回文字符串也是类似的思路。