這個(gè)系列算是出于個(gè)人興趣開的一個(gè)新坑吧，最近看到同學(xué)刷LeetCode算法題，就想寫寫那些可以一行Python代碼寫出來的題目，因此本專欄的文章的解題方式效率不做保證，只為追求“一行的浪漫”。

題目

題解

簡單解釋一下題目，給定一個(gè)字符串s，從中找到一個(gè)子串其中沒有字母重復(fù)且該子串每個(gè)元素在原始字符串也是順序連接的（也就是abc不是abbc的合適子串），輸出最長的子串的長度即可。本題難度為Medium。

代碼

這題的解題思路由不少，我是參考了一個(gè)hashmap的解法做的，它的基本原理是不斷向后遍歷字符串的字符序列，一旦該字符重復(fù)即更新起始點(diǎn)（依靠維護(hù)字典一個(gè)記錄字典），否則一直向后，不斷更新最大長度。這里具體的實(shí)現(xiàn)參考自Discuss的一個(gè)方法，使用了Python3.8支持的賦值表達(dá)式來做到單行傳遞。

from functools import reduceclass Solution:def lengthOfLongestSubstring(self, s: str) -> int:return reduce(lambda a, b: (r := max(a[0], a[2].get(b[1], 0)), max(a[1], b[0] - r + 1), {**a[2], b[1]: b[0] + 1}), enumerate(s), (0, 0, {}))[1]

其中就是利用reduce函數(shù)不斷取連續(xù)的兩個(gè)元素遍歷，當(dāng)然上述代碼理解是有難度的，下面是拆開的可理解版本。

def fn(a, b):"""a: the last elementb: the next element"""start, rst, help = ai, c = bstart = max(start, help.get(c, 0))rst = max(rst, i - start + 1)help[c] = i + 1return start, rst, helpclass Solution:def lengthOfLongestSubstring(self, s: str) -> int:return reduce(fn, enumerate(s), (0, 0, {}))[1]

提交的反饋如下。

總結(jié)

以上是生活随笔為你收集整理的0003-Longest Substring Without Repeating Characters(无重复字符的最长子串)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。