[300 Bài Code Thiếu Nhi] Valid Parentheses – Python

Mô tả bài toán

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

Giải pháp

Giải pháp của mình

Để giải quyết bài toán này, mình sẽ duyệt qua từng ký tự trong chuỗi đồng thời khởi tạo 1 mảng arr để lưu các ký tự đã được duyệt qua. Nếu ký tự cuối của mảng arr khớp với ký tự tiếp theo của chuỗi thì xóa ký tự đó khỏi mảng, nếu không thì thêm ký tự của chuỗi đó vào mảng. Cứ như vậy cho đến khi duyệt hết các ký tự trong chuỗi, nếu mảng arr rỗng thì trả về true, nếu không thì trả về false.

Nhược điểm của giải pháp này là sẽ phải duyệt qua tất cả phần tử của chuỗi rồi mới đưa ra kết quả trong khi có thể chuỗi đã sai ngay từ đầu.

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        arr = []
        for i in s:
            if ( len(arr) > 0 and ((arr[len(arr) - 1] == '(' and i == ')') 
                or (arr[len(arr) - 1] == '[' and i == ']') 
                or (arr[len(arr) - 1] == '{' and i == '}'))):
                arr.pop()
            else:
                arr.append(i)
        if(arr == []):
            return True
        else:
            return False

Giải pháp khác

Mình đã tham khảo khá nhiều giải pháp nhưng tại đây mình sẽ đưa ra cái mà mình cảm thấy đơn giản và dễ hiểu nhất.

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        for x in range(len(s)//2):
            if s=='': return True
            s = s.replace('()', '').replace('{}', '').replace('[]', '')
        return s==''

You need to login in order to like this post: click here