LEETCODE 1392. Longest Happy Prefix 解题思路分析

题目大意：

最长快乐前缀

「快乐前缀」是在原字符串中既是 非空 前缀也是后缀（不包括原字符串自身）的字符串。

给你一个字符串 s，请你返回它的 最长快乐前缀。

如果不存在满足题意的前缀，则返回一个空字符串。

示例 1：

输入：s = "level"
输出："l"
解释：不包括 s 自己，一共有 4 个前缀（"l", "le", "lev", "leve"）和 4 个后缀（"l", "el", "vel", "evel"）。最长的既是前缀也是后缀的字符串是 "l" 。

示例 2：

输入：s = "ababab"
输出："abab"
解释："abab" 是最长的既是前缀也是后缀的字符串。题目允许前后缀在原字符串中重叠。

示例 3：

输入：s = "leetcodeleet"
输出："leet"

示例 4：

输入：s = "a"
输出：""

提示：

• 1 <= s.length <= 10^5
• s 只含有小写英文字母

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1392

解题思路分析：

这道题在比较上没有什么好的逻辑，我们需要从长度为1的前后缀开始，一直比较到长度为length-1为止，也就是说我们需要比较字符串的前1位与后1位是否相同，然后比较前2位与后2位是否相同，以此类推，直到比较完前length-1位与后 length-1位是否相同。如果等长的前后缀子串相同的话，该前缀或者后缀即是一个快乐前缀，由于在循环过程中，前后缀的长度是在不断增加的，因此，最后一个出现的快乐前缀应该是最长结果。

不过这种解法的缺点在于频繁的字符串操作（substring和equals操作）会大幅消耗执行时间，也会导致TLE时间超时。因此我们可以使用字符串的hash值方式来比较前后缀是否相同。这里我们需要普及一个知识点，任意一个字符串的Hash值的计算公式为：

int hash=s[0]∗31^(n−1)+s[1]∗31^(n−2) +...+s[n−2]∗31^1+s[n−1]∗31^0

　

对于前缀hash，每次长度加一后hash的变化应该是：

hash = hash*31 + 新添头字符ch

　

对于后缀hash，每次长度加一后hash的变化应该是：

hash = hash + 新添尾字符*31^t   (t为后缀长度减1)

这样我们每次只需要比较前缀hash与后缀hash是否相同即可。

实现代码：

public String longestPrefix(String s) {
    int hashPre=0; // 前缀hash
    int hashSuff=0; // 后缀hash
    int left=0; // 前缀子串当前下标
    int right=s.length()-1; // 后缀子串当前下标
    int pow=1; // 31的0次方
    int maxLength=0; // 最大快乐前缀长度
    while(left<s.length()-1){
        // 前缀子串加一个字符
        hashPre = hashPre*31+s.charAt(left);
        // 后缀子串加一个字符
        hashSuff=hashSuff+s.charAt(right)*pow;
        // 如果前缀等于后缀
        if(hashPre==hashSuff){
            // 最大长度为当前前缀下标加一
            maxLength = left+1;
        }
        left++; // 前缀下标加一
        right--; // 后缀下标减一
        pow*=31; // 加幂
    }
    return maxLength==0?"":s.substring(0,maxLength);
}

本题解法执行时间为8ms。

Runtime: 8 ms, faster than 92.32% of Java online submissions for Longest Happy Prefix.

Memory Usage: 42.2 MB, less than 100.00% of Java online submissions for Longest Happy Prefix.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1392-longest-happy-prefix-解题思路分析/