LeetCode 1616: Split Two Strings to Make Palindrome
Problem Description
Explanation:
To solve this problem, we can iterate over all possible splitting points in the strings a and b, checking if either aprefix + bsuffix or bprefix + asuffix forms a palindrome. We can iterate from index 0 to length-1, splitting at each index.
For each splitting point, we check if the combined strings form a palindrome by comparing characters from both ends towards the middle. If we find a mismatch, we move on to the next splitting point.
This algorithm has a time complexity of O(n) where n is the length of the strings a and b, as we iterate through the strings once. The space complexity is O(1) as we use constant extra space.
:
Solutions
class Solution {
public boolean checkPalindromeFormation(String a, String b) {
return checkPalindrome(a, b) || checkPalindrome(b, a);
}
private boolean checkPalindrome(String a, String b) {
int i = 0, j = a.length() - 1;
while (i < j && a.charAt(i) == b.charAt(j)) {
i++;
j--;
}
return isPalindrome(a, i, j) || isPalindrome(b, i, j);
}
private boolean isPalindrome(String s, int i, int j) {
while (i < j) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
i++;
j--;
}
return true;
}
}Loading editor...