【字符串2】字符串插入问题

前言

回文字符串讲解

回文字符串是指正着读和反着读都一样的字符串。例如：

• "level" 是回文字符串，因为正着读和反着读都是 "level"。
• "madam" 也是回文字符串。

判断一个字符串是否是回文字符串，可以通过从两端逐一比较字符来实现。如果两端的字符不一样，就不是回文；如果两端的字符完全相同，那么继续向中间移动指针，直到所有字符都被比较完。

例如，对于字符串 "racecar"：

• 从左到右读是 "racecar"。
• 从右到左读也是 "racecar"，因此 "racecar" 是回文字符串。

  字符串切片（Slicing）简介

字符串切片是 Python 中一种强大的操作，它可以帮助我们从字符串中提取出子字符串（即一部分）。通过切片，可以灵活地获取从字符串的任意位置到任意位置的字符，并且还可以控制步长（即跳过某些字符）。

字符串切片的基本语法

string[start:end:step]

• start：切片的起始位置，包含该位置。默认为 0，即从字符串的第一个字符开始。
• end：切片的结束位置，不包含该位置。默认为字符串的末尾，即提取到最后一个字符为止。
• step：步长，表示每次从起始位置到结束位置的跳跃量。默认为 1，即逐个字符获取。

示例

假设我们有一个字符串 s = "abcdefghi"。

s = "abcdefghi"

1. 获取从某个位置到另一个位置的子字符串

s[1:4]   # 从索引 1 到索引 4（不包含索引 4）

输出：

"bcd"

• start = 1，从索引 1 开始取字符，即从字符 'b' 开始。
• end = 4，取到索引 4 之前的字符，即 "bc", "cd", "d"，所以结果是 "bc"。

2. 省略 start 和 end

如果省略 start 或 end，它会默认取从头到尾的子字符串。

s[:]   # 默认取整个字符串

输出：

"abcdefghi"

• 省略了 start 和 end，表示从头到尾取所有字符。

3. 使用步长 step

步长控制了字符的提取间隔。例如，步长为 2 就表示每隔一个字符取一个字符。

s[::2]   # 步长为 2，每隔一个字符取一个

输出：

"acegi"

• 步长为 2，即从字符串中每隔一个字符取一个字符，所以结果是 "acegi"。

4. 省略步长，使用负数步长（反转字符串）

负数步长表示从右到左提取字符（即反向提取）。

s[::-1]   # 步长为 -1，表示反转字符串

输出：

"ihgfedcba"

• step = -1，表示从字符串的最后一个字符开始，逐个取字符，最终得到反转后的字符串。

5. 从指定位置开始，指定步长

你还可以结合使用 start 和 step 来从某个位置开始，以指定的间隔提取字符。

s[1::2]   # 从索引 1 开始，每隔一个字符取一个

输出：

"bdfh"

• start = 1，从索引 1 开始，即从字符 'b' 开始。
• step = 2，每隔一个字符取一个，所以结果是 "bdfh"。

总结

1. start：指定切片的起始位置，默认是 0。
2. end：指定切片的结束位置，默认是字符串的末尾。
3. step：指定步长，控制每次跳过的字符数。默认为 1，可以用来跳过某些字符，或反向提取字符。

切片是非常灵活且强大的工具，适用于从字符串中提取子串、反转字符串、跳过某些字符等多种场景。

题解

题面分析

题目要求将字符串 $B$ 插入到字符串 $A$ 的某个位置，使得新的字符串是一个回文字符串。如果有可能，则输出 "YES"，否则输出 "NO"。

思路

1. 判断回文字符串

回文字符串是指正着读和反着读都一样的字符串。我们需要一个方法来判断一个字符串是否是回文。

• 思路：使用 Python 中的字符串切片技术，我们可以判断一个字符串是否是回文字符串。如果一个字符串 s 和 s[::-1]（反转后的字符串）相等，那么它就是回文字符串。

  • 对应代码：

    if new_string == new_string[::-1]:
        print("YES")
        return
    

    解释：这里 new_string[::-1] 是字符串 new_string 的反转。如果 new_string 和它的反转字符串相等，就说明它是回文。

2. 遍历所有可能的插入位置

我们需要将字符串 B 插入到字符串 A 的每个可能位置，并检查插入后的新字符串是否为回文。

• 思路：遍历字符串 A 的所有插入位置，插入 B 并判断结果字符串是否为回文。对于每一个插入位置 i，我们将 B 插入到 A 的第 i 个位置，生成新的字符串。

  • 对应代码：

    for i in range(len(A) + 1):
        new_string = A[:i] + B + A[i:]
    

    解释：for i in range(len(A) + 1) 遍历 A 字符串的每个可能的插入位置（从 0 到 len(A)）。A[:i] 是 A 中从头到第 i 个字符，A[i:] 是从第 i 个字符到末尾的部分。B 被插入到这两部分之间。

3. 输出结果

当我们找到一个回文字符串时，立即输出 "YES" 并结束程序。如果遍历所有插入位置后都没有找到回文字符串，则输出 "NO"。

• 思路：如果我们找到符合条件的回文字符串，则立即输出 "YES"；否则继续遍历下一个插入位置。如果所有插入位置都检查完毕没有找到回文，则输出 "NO"。

  • 对应代码：

    print("NO")
    

    解释：如果没有找到回文，程序会在遍历完所有插入位置后输出 "NO"。

完整代码

def main():
    # 输入两个字符串 A 和 B
    A = input().strip()  # 输入字符串 A
    B = input().strip()  # 输入字符串 B

    # 遍历 A 字符串的每个位置，尝试插入 B
    for i in range(len(A) + 1):  # 遍历 A 的所有插入位置，i 从 0 到 len(A)
        # 构造新字符串，将 B 插入到 A 的第 i 个位置
        new_string = A[:i] + B + A[i:]
        
        # 判断新字符串是否为回文
        if new_string == new_string[::-1]:  # 判断回文，x == x[::-1]
            print("YES")
            return  # 找到回文，立即返回

    print("NO")  # 如果没有找到回文，输出 NO

if __name__ == "__main__":
    main()

时间复杂度分析

• 插入操作的时间复杂度是 O(n)，其中 n 是字符串 A 的长度。
• 判断回文的时间复杂度是 O(n)，因此总的时间复杂度是 O(n^2)。

题目描述：

给定两个字符串 $A$ 和 $B$，请判断是否可以在字符串 $A$ 的某个位置插入一个字符串 $B$，使得插入后的新字符串成为一个回文串。回文串是指正读和反读都相同的字符串。

说明:可以插入在开头或者结尾

输入：

输入包含两行：

• 第一行：字符串 $A$，其长度为 $n$ $(1 \leq n \leq 100)$，只包含小写字母。
• 第二行：字符串 $B$，其长度为 $m$ $(1 \leq m \leq 100)$，只包含小写字母。

输出：

如果可以插入字符串 $B$ 使得字符串 $A$ 变成回文串，输出 "YES"；否则，输出 "NO"。

样例输入：

abca
b

样例输出：

YES

提示：

• 在样例输入中，将字符串 $B$ 插入字符串 $A$ 的位置，例如在 $c$ 和 $a$ 之间，可以形成回文串 "abcbа"，因此输出 "YES"。