分割两个字符串得到回文串【LC1616】
给你两个字符串
a
和b
,它们长度相同。请你选择一个下标,将两个字符串都在 相同的下标 分割开。由a
可以得到两个字符串:aprefix
和asuffix
,满足a = aprefix + asuffix
,同理,由b
可以得到两个字符串bprefix
和bsuffix
,满足b = bprefix + bsuffix
。请你判断aprefix + bsuffix
或者bprefix + asuffix
能否构成回文串。当你将一个字符串
s
分割成sprefix
和ssuffix
时,ssuffix
或者sprefix
可以为空。比方说,s = "abc"
那么"" + "abc"
,"a" + "bc"
,"ab" + "c"
和"abc" + ""
都是合法分割。如果 能构成回文字符串 ,那么请返回
true
,否则返回false
。注意,
x + y
表示连接字符串x
和y
。
分割点没有判断好 加油
- 思路
实现
class Solution { public boolean checkPalindromeFormation(String a, String b) { return check(a, b) || check(b, a); } public boolean check(String a, String b){ int i = 0, j = b.length() - 1; while (i < j && a.charAt(i) == b.charAt(j)){ i++; j--; } return i >= j || isPalindrome(a, i, j) || isPalindrome(b, i, j); } public boolean isPalindrome(String s, int i, int j){ while (i < j && s.charAt(i) == s.charAt(j)){ i++; j--; } return i >= j; } }
复杂度分析
时间复杂度:O ( n )
空间复杂度:O ( 1 )