題目描述：
給你兩個字串 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 ，
示例 1：
輸入：a = "x", b = "y"
輸出：true
解釋：如果 a 或者 b 是回文串，那么答案一定為 true ，因為你可以如下分割：
aprefix = "", asuffix = "x"
bprefix = "", bsuffix = "y"
那么 aprefix + bsuffix = "" + "y" = "y" 是回文串，
示例 2：
輸入：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 都只包含小寫英文字母
解題思路：
1）、由于切分的下標是一致的，也就是說 aprefix.length() = bprefix.length() && asuffix.length() = bsuffix.length() ;
判斷的是 aprefix + bsuffix 或者 bprefix + asuffix 是否是回文；
2）、分析如圖所示：（是否能夠相遇 即 start >= over）
代碼實作：
class Solution {
public:
// 判斷aprefix + bsuffix 是否是回文 ；
bool getAnswer(string& a, string& b) {
int start = 0 , over = a.length() - 1 , i , j ;
// 圖 1）
while (start < over) {
if (a[start] == b[over]) {
start ++ ;
over -- ;
} else break ;
}
i = start , j = over ;
// 圖 2）
while (i < j) {
if (b[i] == b[j]) {
i ++ ;
j -- ;
} else break ;
}
if (i >= j) return true ;
i = start , j = over ;
// 圖 3）
while (i < j) {
if (a[i] == a[j]) {
i ++ ;
j -- ;
} else break ;
}
if (i >= j) return true ;
else return false ;
}
bool checkPalindromeFormation(string a, string b) {
if (getAnswer(a , b) || getAnswer(b , a)) return true ;
else return false ;
}
};
復雜度計算：
時間復雜度：O(n) ；
空間復雜度：O(1) ；
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/168815.html
標籤：其他
上一篇：2020-10-10