Skip to content

Latest commit

 

History

History
248 lines (194 loc) · 7.35 KB

File metadata and controls

248 lines (194 loc) · 7.35 KB
comments difficulty edit_url rating source tags
true
中等
1868
第 210 场周赛 Q3
双指针
字符串

English Version

题目描述

给你两个字符串 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 都只包含小写英文字母

解法

方法一:双指针

我们可以使用双指针,其中一个指针 $i$ 从字符串 $a$ 的头部开始,另一个指针 $j$ 从字符串 $b$ 的尾部开始,如果两个指针指向的字符相等,那么两个指针同时往中间移动,直到遇到不同的字符或两指针交叉。

如果两指针交叉,即 $i \geq j$,说明 $prefix$$suffix$ 已经可以得到回文串,返回 true;否则,我们还需要判断 $a[i,...j]$ 或者 $b[i,...j]$ 是否是回文串,若是,返回 true

否则,我们尝试交换两个字符串 $a$$b$,重复上述同样的过程。

时间复杂度 $O(n)$,空间复杂度 $O(1)$。其中 $n$ 是字符串 $a$$b$ 的长度。

Python3

class Solution:
    def checkPalindromeFormation(self, a: str, b: str) -> bool:
        def check1(a: str, b: str) -> bool:
            i, j = 0, len(b) - 1
            while i < j and a[i] == b[j]:
                i, j = i + 1, j - 1
            return i >= j or check2(a, i, j) or check2(b, i, j)

        def check2(a: str, i: int, j: int) -> bool:
            return a[i : j + 1] == a[i : j + 1][::-1]

        return check1(a, b) or check1(b, a)

Java

class Solution {
    public boolean checkPalindromeFormation(String a, String b) {
        return check1(a, b) || check1(b, a);
    }

    private boolean check1(String a, String b) {
        int i = 0;
        int j = b.length() - 1;
        while (i < j && a.charAt(i) == b.charAt(j)) {
            i++;
            j--;
        }
        return i >= j || check2(a, i, j) || check2(b, i, j);
    }

    private boolean check2(String a, int i, int j) {
        while (i < j && a.charAt(i) == a.charAt(j)) {
            i++;
            j--;
        }
        return i >= j;
    }
}

C++

class Solution {
public:
    bool checkPalindromeFormation(string a, string b) {
        return check1(a, b) || check1(b, a);
    }

private:
    bool check1(string& a, string& b) {
        int i = 0, j = b.size() - 1;
        while (i < j && a[i] == b[j]) {
            ++i;
            --j;
        }
        return i >= j || check2(a, i, j) || check2(b, i, j);
    }

    bool check2(string& a, int i, int j) {
        while (i <= j && a[i] == a[j]) {
            ++i;
            --j;
        }
        return i >= j;
    }
};

Go

func checkPalindromeFormation(a string, b string) bool {
	return check1(a, b) || check1(b, a)
}

func check1(a, b string) bool {
	i, j := 0, len(b)-1
	for i < j && a[i] == b[j] {
		i++
		j--
	}
	return i >= j || check2(a, i, j) || check2(b, i, j)
}

func check2(a string, i, j int) bool {
	for i < j && a[i] == a[j] {
		i++
		j--
	}
	return i >= j
}

TypeScript

function checkPalindromeFormation(a: string, b: string): boolean {
    const check1 = (a: string, b: string) => {
        let i = 0;
        let j = b.length - 1;
        while (i < j && a.charAt(i) === b.charAt(j)) {
            i++;
            j--;
        }
        return i >= j || check2(a, i, j) || check2(b, i, j);
    };

    const check2 = (a: string, i: number, j: number) => {
        while (i < j && a.charAt(i) === a.charAt(j)) {
            i++;
            j--;
        }
        return i >= j;
    };
    return check1(a, b) || check1(b, a);
}

Rust

impl Solution {
    pub fn check_palindrome_formation(a: String, b: String) -> bool {
        fn check1(a: &[u8], b: &[u8]) -> bool {
            let (mut i, mut j) = (0, b.len() - 1);
            while i < j && a[i] == b[j] {
                i += 1;
                j -= 1;
            }
            if i >= j {
                return true;
            }
            check2(a, i, j) || check2(b, i, j)
        }

        fn check2(a: &[u8], mut i: usize, mut j: usize) -> bool {
            while i < j && a[i] == a[j] {
                i += 1;
                j -= 1;
            }
            i >= j
        }

        let a = a.as_bytes();
        let b = b.as_bytes();
        check1(a, b) || check1(b, a)
    }
}