0020. Valid Parentheses | LeetCode Cookbook

[halfrost]

https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0020.Valid-Parentheses/

[yngwiewang]

请问这道题的时间复杂度为什么是log(N)而不是O(N)?

[halfrost]

@yngwiewang 请问这道题的时间复杂度为什么是log(N)而不是O(N)?

是 O(N) 呀，在哪里看到的 log(N)？

[hujun2020]

喜欢简单题

[chiyoi]

python打卡

s = input("Input: s = ")

class na:
    def neko():
        stack = []
        for character in list(s):
            opposite = {')': '(', '}': '{', ']': '['}
            if character in {'(', '{', '['}:
                stack.append(character)
            elif len(stack) and stack[-1] == opposite[character]:
                stack.pop()
            else:
                return False
        return not len(stack)

print("Output: {0}".format(na.neko()))

只有84%，在哪浪费时间了呢……

[chiyoi]

@halfrost

@yngwiewang 请问这道题的时间复杂度为什么是log(N)而不是O(N)?

是 O(N) 呀，在哪里看到的 log(N)？

第二章 2.05 页面上是这么写的。话说小于O(n)的算法真的存在吗？都不用检查完所有输入的？

[halfrost]

python打卡

s = input("Input: s = ")

class na:
    def neko():
        stack = []
        for character in list(s):
            opposite = {')': '(', '}': '{', ']': '['}
            if character in {'(', '{', '['}:
                stack.append(character)
            elif len(stack) and stack[-1] == opposite[character]:
                stack.pop()
            else:
                return False
        return not len(stack)

print("Output: {0}".format(na.neko()))

只有84%，在哪浪费时间了呢……

@CHIYOI 我看你的解题思路没有问题，再想提高 runtime time 可能要从语言层面上下手了，我对 Python 还不是特别熟悉，暂时还给不了你提高时间的建议，你可以看看 discussion 里面别人的代码，看看比你时间更优的代码，他们是怎么写的。

[halfrost]

@halfrost

@yngwiewang 请问这道题的时间复杂度为什么是log(N)而不是O(N)?

是 O(N) 呀，在哪里看到的 log(N)？

第二章 2.05 页面上是这么写的。话说小于O(n)的算法真的存在吗？都不用检查完所有输入的？

@CHIYOI 我们写的这个 solution 外层的输入函数，不计算时间的。时间复杂度仅针对我们写的这个函数。小于 O(n) 的算法有 O(1) ，O(log n) 和 O(sqrt(n))。

[suntong]

Simplified as:

func isValid(s string) bool {
	// 空字符串直接返回 true
	if len(s) == 0 {
		return true
	}
	m := make(map[rune]rune)
	m['('] = ')'
	m['['] = ']'
	m['{'] = '}'

	stack := make([]rune, 0)
	for _, v := range s {
		if _, ok := m[v]; ok {
			stack = append(stack, v)
		} else if len(stack) > 0 && m[stack[len(stack)-1]] == v {
			stack = stack[:len(stack)-1]
		} else {
			return false
		}
	}
	return len(stack) == 0
}

Tested at: https://github.com/suntong/lang/tree/master/lang/Go/src/ds/LeetCode/0020.Valid-Parentheses

[halfrost]

@suntong 欢迎提交 PR

[suntong]

OK, sure, will do, but not now, as I'm busy job hunting at the moment, 😭😭

[tanggaolin]

@suntong Simplified as:

func isValid(s string) bool {
	// 空字符串直接返回 true
	if len(s) == 0 {
		return true
	}
	m := make(map[rune]rune)
	m['('] = ')'
	m['['] = ']'
	m['{'] = '}'

	stack := make([]rune, 0)
	for _, v := range s {
		if _, ok := m[v]; ok {
			stack = append(stack, v)
		} else if len(stack) > 0 && m[stack[len(stack)-1]] == v {
			stack = stack[:len(stack)-1]
		} else {
			return false
		}
	}
	return len(stack) == 0
}

Tested at: https://github.com/suntong/lang/tree/master/lang/Go/src/ds/LeetCode/0020.Valid-Parentheses

赞赞