跳到主要内容

1616.分割两个字符串得到回文串

· 阅读需 4 分钟

1、题干​

给你两个字符串 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 = "abdef", b = "fecab"
输出：true

示例 3：

输入：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 都只包含小写英文字母

2、思路​

这是回文判断的升级版，考虑4种情况：

  • 字符串1是回文
  • 字符串2是回文
  • 字符串1前缀+字符串2后缀是回文
  • 字符串2前缀+字符串1后缀是回文

实际上前面两种情况可以忽略


具体实现时，可以将常规的回文判断做成辅助函数并扩展：

  • 使用两个字符串作为入参，不同于常规回文，这里需要同时判断两串字符
  • 考虑双串组合的情况，增加一个入参 i，用于标识双串组合的起始位置
  • 遍历过程中如果遇到前后不匹配的字符，则考虑两种情况：
    • 双串相等，可以判定不是回文
    • 双串不等，则判断从该位置开始，如果其中任意一个字符串仍符合回文特性，则返回 true，反之为 false

3、代码​

function checkPalindromeFormation(s1: string, s2: string): boolean {
    function isPdr(a: string, b: string, i: number = 0) {
        for (; i < a.length / 2 >> 0; i++) {
            if (a[i] !== b[a.length - i - 1]) return a === b ? false : isPdr(a, a, i) || isPdr(b, b, i);
        }
        return true;
    }
    return isPdr(s1, s2) || isPdr(s2, s1);
};

4、复杂度​

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(1)O(1)

5、执行结果​

image.png