LeetCode trên chuỗi con Palindromic dài nhất bằng Python

Question

Đây là một câu hỏi lập trình từ LeetCode :

Cho một chuỗi s, trả về chuỗi con palindromic dài nhất tính bằng s.

Ví dụ 1:

Đầu vào: s = "babad" Đầu ra: "bab" Lưu ý: "aba" cũng là một câu trả lời hợp lệ.

Dưới đây là mã của tôi không thành công khi nhập sau do "Đã vượt quá giới hạn thời gian":

""

class Solution(object):

    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) == 0:
            return None
        if len(s) == 1:
            return s

        P = [[False]*len(s) for i in range(len(s))]

        for i in range(len(s)):
            P[i][i]   = True

        for i in range(len(s)-1):
            P[i][i+1] = (s[i]==s[i+1])

        for s_len in range(3,len(s)+1):
            for i in range(len(s)+1-s_len):
                P[i][i+s_len-1] = P[i+1][i+s_len-2] and (s[i]==s[i+s_len-1])

        ip = 0
        jp = 0
        max_len = 1

        for i in range(len(s)):
            for j in range(len(s)):
                if P[i][j] and j+1-i > max_len:
                    max_len = j+1-i
                    ip = i
                    jp = j 
                    continue

        return s[ip:jp+1]

Tôi đang cố gắng làm theo cách tiếp cận sau được mô tả trong giải pháp trang web. Bất cứ ai có thể giúp xem làm thế nào để làm cho mã của tôi hiệu quả hơn?

---

Answer 1

Tuyên bố từ chối trách nhiệm: Không phải là Người đánh giá mã

Đây là một số nhận xét ngắn mặc dù:

• Bạn đang lặp lại mặc dù hai lần.
• Điều đó sẽ làm cho nó trở nên vũ phu.
• Brute force thường không thành công đối với một số câu hỏi trung bình và khó trên LeetCode.

Giải pháp thay thế

• Ở đây chúng tôi sẽ lặp lại một lần:

class Solution:
    def longestPalindrome(self, s):
        if len(s) < 1:
            return s

        def isPalindrome(left, right):
            return s[left:right] == s[left:right][::-1]

        left, right = 0, 1
        for index in range(1, len(s)):
            if index - right > 0 and isPalindrome(index - right - 1, index + 1):
                left, right = index - right - 1, right + 2
            if index - right >= 0 and isPalindrome(index - right, index + 1):
                left, right = index - right, right + 1
        return s[left: left + right]

Giải pháp của bạn

• Tôi vừa thử nghiệm giải pháp của bạn (vượt qua một chút):

class Solution(object):

    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) < 1:
            return s

        P = [[False] * len(s) for i in range(len(s))]

        for i in range(len(s)):
            P[i][i] = True

        for i in range(len(s) - 1):
            P[i][i + 1] = (s[i] == s[i + 1])

        for s_len in range(3, len(s) + 1):
            for i in range(len(s) + 1 - s_len):
                P[i][i + s_len - 1] = P[i + 1][i + s_len - 2] and (s[i] == s[i + s_len - 1])

        ip = 0
        jp = 0
        max_len = 1

        for i in range(len(s)):
            for j in range(len(s)):
                if P[i][j] and j + 1 - i > max_len:
                    max_len = j + 1 - i
                    ip = i
                    jp = j
                    continue

        return s[ip:jp + 1]

• Vì thời gian chạy cao nên đôi khi nó có thể bị lỗi.

• Tôi đoán LeetCode có giới hạn thời gian cho mỗi vấn đề, có lẽ 10 giây sẽ là giới hạn cho vấn đề cụ thể này.

• Có thể dựa trên vị trí địa lý / thời gian, thời gian chạy cũng sẽ khác nhau.

---

Chỉ cần tối ưu hơn một chút:

• Vui lòng xem dòng này for j in range(i + 1, len(s))::

class Solution(object):

    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) < 1:
            return s

        P = [[False] * len(s) for _ in range(len(s))]

        for i in range(len(s)):
            P[i][i] = True

        for i in range(len(s) - 1):
            P[i][i + 1] = (s[i] == s[i + 1])

        for s_len in range(3, len(s) + 1):
            for i in range(len(s) + 1 - s_len):
                P[i][i + s_len - 1] = P[i + 1][i + s_len - 2] and (s[i] == s[i + s_len - 1])

        ip = 0
        jp = 0
        max_len = 1

        for i in range(len(s)):
            for j in range(i + 1, len(s)):
                if P[i][j] and j + 1 - i > max_len:
                    max_len = j + 1 - i
                    ip = i
                    jp = j
                    continue

        return s[ip:jp + 1]

• Nó giảm khoảng 1 giây nhưng vẫn không ổn.

• Tôi chắc rằng có nhiều cách để tối ưu hóa hơn.

• Chờ một chút! Có những người đánh giá Python tốt ở đây. Có thể sẽ giúp bạn ra ngoài.

---

Với một số nhận xét:

class Solution:
    def longestPalindrome(self, s):
        if len(s) < 1:
            return s

        def isPalindrome(left, right):
            return s[left:right] == s[left:right][::-1]

        # We set the left pointer on the first index
        # We set the right pointer on the second index
        # That's the minimum true palindrome
        left, right = 0, 1

        # We visit the alphabets from the second index forward once
        for index in range(1, len(s)):
            # Here we move the right pointer twice and once checking for palindromeness
            # We boundary check using index - right, to remain positive
            if index - right > 0 and isPalindrome(index - right - 1, index + 1):
                print(f"Step {index - 1}: Left pointer is at {index - right - 1} and Right pointer is at {index + 1}")
                print(f"Palindromeness start: {index - right - 1} - Palindromeness end: {index + 1}")
                print(f"Window length: {right}")
                print(f"Before: Left is {left} and Right is {left + right}")
                left, right = index - right - 1, right + 2
                print(f"After: Left is {left} and Right is {left + right}")
                print(f"String: {s[left: left + right]}")
                print('#' * 50)
            if index - right >= 0 and isPalindrome(index - right, index + 1):
                print(f"Step {index - 1}: Left pointer is at {index - right} and Right pointer is at {index + 1}")
                print(f"Palindromeness start: {index - right - 1} - Palindromeness end: {index + 1}")
                print(f"Window length: {right + 1}")
                print(f"Before: Left is {left} and Right is {left + right}")
                left, right = index - right, right + 1
                print(f"After: Left is {left} and Right is {left + right}")
                print(f"String: {s[left: left + right]}")
                print('#' * 50)
        return s[left: left + right]


Solution().longestPalindrome("glwhcebdjbdroiurzfxxrbhzibilmcfasshhtyngwrsnbdpzgjphujzuawbebyhvxfhtoozcitaqibvvowyluvdbvoqikgojxcefzpdgahujuxpiclrrmalncdrotsgkpnfyujgvmhydrzdpiudkfchtklsaprptkzhwxsgafsvkahkbsighlyhjvbburdfjdfvjbaiivqxdqwivsjzztzkzygcsyxlvvwlckbsmvwjvrhvqfewjxgefeowfhrcturolvfgxilqdqvitbcebuooclugypurlsbdfquzsqngbscqwlrdpxeahricvtfqpnrfwbyjvahrtosovsbzhxtutyfjwjbpkfujeoueykmbcjtluuxvmffwgqjgrtsxtdimsescgahnudmsmyfijtfrcbkibbypenxnpiozzrnljazjgrftitldcueswqitrcvjzvlhionutppppzxoepvtzhkzjetpfqsuirdcyqfjsqhdewswldawhdyijhpqtrwgyfmmyhhkrafisicstqxokdmynnnqxaekzcgygsuzfiguujyxowqdfylesbzhnpznayzlinerzdqjrylyfzndgqokovabhzuskwozuxcsmyclvfwkbimhkdmjacesnvorrrvdwcgfewchbsyzrkktsjxgyybgwbvktvxyurufsrdufcunnfswqddukqrxyrueienhccpeuqbkbumlpxnudmwqdkzvsqsozkifpznwapxaxdclxjxuciyulsbxvwdoiolgxkhlrytiwrpvtjdwsssahupoyyjveedgqsthefdyxvjweaimadykubntfqcpbjyqbtnunuxzyytxfedrycsdhkfymaykeubowvkszzwmbbjezrphqildkmllskfawmcohdqalgccffxursvbyikjoglnillapcbcjuhaxukfhalcslemluvornmijbeawxzokgnlzugxkshrpojrwaasgfmjvkghpdyxt")

Bản in:

Step 18: Left pointer is at 18 and Right pointer is at 20
Palindromeness start: 17 - Palindromeness end: 20
Window length: 2
Before: Left is 0 and Right is 1
After: Left is 18 and Right is 20
String: xx
##################################################
Step 25: Left pointer is at 24 and Right pointer is at 27
Palindromeness start: 23 - Palindromeness end: 27
Window length: 3
Before: Left is 18 and Right is 20
After: Left is 24 and Right is 27
String: ibi
##################################################
Step 462: Left pointer is at 460 and Right pointer is at 464
Palindromeness start: 459 - Palindromeness end: 464
Window length: 4
Before: Left is 24 and Right is 27
After: Left is 460 and Right is 464
String: pppp
##################################################

Chúc bạn mã hóa vui vẻ! (ˆ_ˆ)