This is the first day of my participation in the August More Text challenge

describe

A string is called a happy prefix if is a non-empty prefix which is also a suffix (excluding itself).

Given a string s, return the longest happy prefix of s. Return an empty string “” if no such prefix exists.

Example 1:

Input: s = "level"
Output: "l"
Explanation: s contains 4 prefix excluding itself ("l", "le", "lev", "leve"), and suffix ("l", "el", "vel", "evel"). The largest prefix which is also suffix is given by "l".
Copy the code

Example 2:

Input: s = "ababab"
Output: "abab"
Explanation: "abab" is the largest prefix which is also suffix. They can overlap in the original string.
Copy the code

Example 3:

Input: s = "leetcodeleet"
Output: "leet"
Copy the code

Example 4:

Input: s = "a"
Output: ""
Copy the code

Note:

1 <= s.length <= 10^5
s contains only lowercase English letters.
Copy the code

parsing

A. the longest common prefix b. the longest happy prefix C. the longest happy prefix D. the longest happy prefix

For example: First, we need to know what prefix and suffix are. We will not explain the meaning of “level” in Example 1. All prefixes are (” L “, “le”, “Lev “, “leve”). All suffixes are (“l”, “el”, “vel”, “evel”). That’s literally what it means, which all of you in this room with high quality XDM will understand.

Objective: To find the longest string with both prefix and suffix based on the given s. If s is an empty string or length 1, return the empty string.

Find the longest common prefix and suffix string. The longest common prefix and suffix string is the longest one. Because the constraint is obvious and the length of S could be one hundred thousand, you would expect a timeout.

answer

class Solution(object):
    def longestPrefix(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s or len(s)==1:return ""
        for i in range(len(s)-1, 0, -1):
            a = s[:i]
            b = s[-i:]
            if a == b:
                return s[:i]
        return ""
        	      
		
Copy the code

The results

Time Limit Exceeded
Copy the code

parsing

In addition, we’ve learned about XDM algorithms, and we’ve heard more or less of the famous KMP algorithm, which is the algorithm for quickly matching substrings within strings. The core of this algorithm is to find the longest common prefix and suffix, so we can use the gods’ improved algorithm to solve this problem. The main idea is to define a next list. Next [j] represents the length of the longest common prefix and suffix in the substring P[0] to P[J-1] in the pattern string P. Specific details are more complex, bebug code can be understood twice, or you can refer to the big guy’s explanation: blog.csdn.net/weixin_3956…

answer

class Solution(object): def longestPrefix(self, s): """ :type s: str :rtype: str """ if not s or len(s)==1:return "" index= 0 m = len(s) next = [0] * m i = 1 while i < m: if (s[i] == s[index]): next[i] = index + 1 index += 1 i += 1 elif (index ! = 0): index = next[index - 1] else: next[i] = 0 i += 1 return s[:next[-1]]Copy the code

The results

Each node in the Python online submission list is linked to the node. Memory Usage: 10000 ms Each node in the Python online submission list for Longest Happy Prefix.Copy the code

Original link: leetcode.com/problems/lo…

Your support is my biggest motivation