4ier's Blog

Solution for Valid Parentheses

06 Aug 2018

Valid Parentheses

  • 使用栈匹配括号

通过栈这种数据结构可以很好的解决符号匹配问题：

  1. 判定栈顶元素是否和当前元素匹配，例如'('和')'匹配
  2. 如果匹配那么pop，如果不匹配那么append
  3. 最后查看栈的长度是否为0

当输入字符串的长度无法被2整除时，可以判定一定不是正确的字符串

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        matchPairs = {
            '(':')',
            '[':']',
            '{':'}',
            ')':'(',
            ']':'[',
            '}':'{'}

        stack = []
        if len(s) % 2 != 0:
            return False
        
        for char in s:
            if stack and matchPairs[stack[-1]] == char:
                stack.pop()
            else:
                stack.append(char)
        
        return 0 == len(stack)

Solution for Roman to Integer

05 Aug 2018

Roman to Integer

  • 倒序遍历求值

罗马数字存在以下特征：

key value
I 1
IV 4
V 5
IX 9
X 10
XL 40
L 50
XC 90
C 100
CD 400
D 500
CM 900
M 1000

Solution for Longest Common Prefix

05 Aug 2018

Longest Common Prefix

  • 求一组字符串最长的相同前缀

思路如下：

  1. 先找到这组字符串长度最短的一个
  2. 遍历这个字符串，同时对比其他字符串相同位置的字符是否相等
  3. 如果不相等，不再继续比较，直接返回当前字符串开头到当前位置的字串
class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ""
        if len(strs) == 1:
            return strs[0]

        sortedStrs = sorted(strs,key=len)
        shortest = sortedStrs[0]

        if len(shortest) == 0:
            return ""

        for i, char in enumerate(shortest):
            for other in sortedStrs[1:]:
                if other[i] != char:
                    return shortest[:i]
        return shortest