8000 added python solution for 002 · monkeyking/LeetCode@1df8968 · GitHub
[go: up one dir, main page]
Skip to content
8000

Commit 1df8968

Browse files
pezypezy
committed
added python solution for 002
1 parent 4a2518c commit 1df8968

File tree

4 files changed

+50
-17
lines changed

4 files changed

+50
-17
lines changed

‎002. Longest Substring Without Repeating Characters/README.md

Lines changed: 13 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,19 @@
1+
# 思路(C++)
2+
3+
此题需要好好读懂题意：**没有重复字符**的最长子字符串的**长度**。
4+
5+
首先，求的只是长度，那么一定有一个 trace 来边记录边比较(max)。
6+
其次，没有重复字符几乎是唯一条件，那么检查重复显然用 k-v mapping.
7+
最后，要考虑一次迭代过程中，如何度量这个长度。
8+
9+
----
10+
111
设 substr 的起点为 start(s), 终点为 last(l). 每一次迭代，记录一张索引表。
212

313
abcabcbb
414
^ ^
515
s l
6-
16+
717
|char|pos|
818
|:--:|:-:|
919
| a | 0 |
@@ -25,7 +35,6 @@ cache[s[last]] = last;
2535

2636
注意最终还需要比较一次，返回 `max(ret, s.size() - start)`
2737

38+
## Python
2839

29-
30-
31-
40+
思路与 C++ 完全一致。

‎002. Longest Substring Without Repeating Characters/solution.h

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -8,16 +8,16 @@ using std::max;
88
class Solution {
99
public:
1010
int lengthOfLongestSubstring(string s) {
11-
size_t ret=0, start=0;
12-
unordered_map<char, size_t> cache = {{s.front(), 0} 10000 };
13-
for (size_t last=1; last < s.size(); ++last) {
14-
auto found = cache.find(s[last]);
15-
if (found != cache.end() && found->second >= start) {
16-
ret = max(ret, last - start);
11+
size_t ret = 0, start = 0;
12+
unordered_map<char, size_t> trace;
13+
for (size_t i = 0; i < s.size(); ++i) {
14+
auto found = trace.find(s[i]);
15+
if (found != trace.end() && found->second >= start) {
16+
ret = max(ret, i - start);
1717
start = found->second + 1;
1818
}
19-
cache[s[last]] = last;
19+
trace[s[i]] = i;
2020
}
21-
return max(ret, s.size()-start);
21+
return max(ret, s.size() - start);
2222
}
2323
};

‎002. Longest Substring Without Repeating Characters/solution.py

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
#!python3
2+
3+
4+
class Solution:
5+
def lengthOfLongestSubstring(self, s):
6+
"""
7+
:type s: str
8+
:rtype: int
9+
"""
10+
rlen = 0
11+
start = 0
12+
trace = {}
13+
for index, ch in enumerate(s):
14+
if ch in trace and trace[ch] >= start:
15+
rlen = max(rlen, index - start)
16+
start = trace[ch] + 1
17+
trace[ch] = index
18+
return max(rlen, len(s) - start)
19+
20+
21+
if __name__ == "__main__":
22+
print(Solution().lengthOfLongestSubstring("abcabcbb") == 3)
23+
print(Solution().lengthOfLongestSubstring("abba") == 2)
24+
print(Solution().lengthOfLongestSubstring("pwwkew") == 3)

‎README.md

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -3,11 +3,11 @@ LeetCode
33

44
LeetCode solutions in C++ 11 and Python3.
55

6-
|NO.|Title|Solution|Note|Difficulty|
7-
|---|-----|--------|--------|----------|
8-
|0|[Two Sum](https://leetcode.com/problems/two-sum)|[C++](000.%20Two%20Sum/solution.h) [Python](000.%20Two%20Sum/solution.py)|[Note](000.%20Two%20Sum)|Easy|
9-
|1|[Add Two Numbers](https://leetcode.com/problems/add-two-numbers)|[C++](001.%20Add%20Two%20Numbers/solution.h) [Python](001.%20Add%20Two%20Numbers/solution.py)|[Note](001.%20Add%20Two%20Numbers)|Medium|
10-
|2|[Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters)|[C++](002.%20Longest%20Substring%20Without%20Repeating%20Characters/solution.h) [Python](002.%20Longest%20Substring%20Without%20Repeating%20Characters/solution.py)|[Note](002.%20Longest%20Substring%20Without%20Repeating%20Characters)|Medium|
6+
|NO.|Title|Solution|Note|Difficulty|Tag|
7+
|---|-----|--------|----|----------|---|
8+
|0|[Two Sum](https://leetcode.com/problems/two-sum)|[C++](000.%20Two%20Sum/solution.h) [Python](000.%20Two%20Sum/solution.py)|[Note](000.%20Two%20Sum)|Easy|`Mapping`|
9+
|1|[Add Two Numbers](https://leetcode.com/problems/add-two-numbers)|[C++](001.%20Add%20Two%20Numbers/solution.h) [Python](001.%20Add%20Two%20Numbers/solution.py)|[Note](001.%20Add%20Two%20Numbers)|Medium|`Linked List`|
10+
|2|[Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters)|[C++](002.%20Longest%20Substring%20Without%20Repeating%20Characters/solution.h) [Python](002.%20Longest%20Substring%20Without%20Repeating%20Characters/solution.py)|[Note](002.%20Longest%20Substring%20Without%20Repeating%20Characters)|Medium|`Mapping`|
1111
|3|[Median of Two Sorted Arrays](https://leetcode.com/problems/median-of-two-sorted-arrays)|[C++](003.%20Median%20of%20Two%20Sorted%20Arrays/solution.h) [Python](003.%20Median%20of%20Two%20Sorted%20Arrays/solution.py)|[Note](003.%20Median%20of%20Two%20Sorted%20Arrays)|Hard|
1212
|4|[Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring)|[C++](004.%20Longest%20Palindromic%20Substring/solution.h) [Python](004.%20Longest%20Palindromic%20Substring/solution.py)|[Note](004.%20Longest%20Palindromic%20Substring)|Medium|
1313
|5|[ZigZag Conversion](https://leetcode.com/problems/zigzag-conversion)|[C++](005.%20ZigZag%20Conversion/solution.h) [Python](005.%20ZigZag%20Conversion/solution.py)|[Note](005.%20ZigZag%20Conversion)|Medium|

0 commit comments

Comments
 (0)
0