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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。