当前位置: 面试刷题>> 最短回文串 (经典算法题500道)


题目描述补充

题目:最短回文串

给定一个字符串 s,要求找到在 s 的右侧添加最少的字符(可以是原字符串中的字符),使得新的字符串成为一个回文串。返回这个最短回文串的右侧添加部分,以及这个添加部分的长度。

示例 1:

输入: s = "abcabc"
输出: "abc"
解释: 最短回文串是 "abcabcabc",在原字符串右侧添加了 "abc"。

示例 2:

输入: s = "a"
输出: ""
解释: 最短回文串就是原字符串 "a",不需要添加任何字符。

PHP 代码示例

function shortestPalindrome($s) {
    $reversed = strrev($s); // 反转字符串
    $concat = $s . '#' . $reversed; // 拼接原字符串、分隔符和反转字符串
    $n = strlen($concat);

    // 使用KMP算法中的部分匹配表(next数组)来找到最长公共前后缀
    $lps = array_fill(0, $n, 0);
    $j = 0;
    $i = 1;
    while ($i < $n) {
        if ($concat[$i] == $concat[$j]) {
            $lps[$i] = $j + 1;
            $i++;
            $j++;
        } elseif ($j != 0) {
            $j = $lps[$j - 1];
        } else {
            $lps[$i] = 0;
            $i++;
        }
    }

    // lps数组中的最后一个值即是最长公共前后缀的长度
    // 需要添加的字符是反转字符串中去掉最长公共前后缀的部分
    return substr($reversed, 0, $n - 1 - $lps[$n - 1]);
}

// 测试
echo shortestPalindrome("abcabc"); // 输出 "abc"
echo shortestPalindrome("a"); // 输出 ""

Python 代码示例

def shortestPalindrome(s: str) -> str:
    reversed_s = s[::-1]  # 反转字符串
    concat = s + '#' + reversed_s  # 拼接字符串
    n = len(concat)
    
    # 使用KMP算法求部分匹配表(next数组)
    lps = [0] * n
    j = 0
    i = 1
    while i < n:
        if concat[i] == concat[j]:
            lps[i] = j + 1
            i += 1
            j += 1
        elif j != 0:
            j = lps[j - 1]
        else:
            lps[i] = 0
            i += 1
    
    # 去掉最长公共前后缀的部分
    return reversed_s[:n - 1 - lps[-1]]

# 测试
print(shortestPalindrome("abcabc"))  # 输出 "abc"
print(shortestPalindrome("a"))  # 输出 ""

JavaScript 代码示例

function shortestPalindrome(s) {
    const reversed = s.split('').reverse().join(''); // 反转字符串
    const concat = s + '#' + reversed; // 拼接字符串
    const n = concat.length;
    
    // 使用KMP算法求部分匹配表(next数组)
    const lps = new Array(n).fill(0);
    let j = 0;
    for (let i = 1; i < n; i++) {
        if (concat[i] === concat[j]) {
            lps[i] = j + 1;
            j++;
        } else if (j !== 0) {
            j = lps[j - 1];
        }
    }
    
    // 去掉最长公共前后缀的部分
    return reversed.substring(0, n - 1 - lps[n - 1]);
}

// 测试
console.log(shortestPalindrome("abcabc")); // 输出 "abc"
console.log(shortestPalindrome("a")); // 输出 ""

码小课网站中有更多相关内容分享给大家学习,涵盖算法、数据结构、编程语言等多个方面,帮助大家提升编程能力。

推荐面试题