适合对算法一窍不通的初学者。
本专栏目前还没有什么读者，食用后请点赞支持一下我的专栏，让更多人看到。
本人对写文章没有太多经验，有宝贵意见和建议请直接留言或者私信告诉我，万分感谢。
为弱化语言特性，本文使用python.
Longest Substring Without Repeating Characters - LeetCodeleetcode.com
图标
image
1.审题
题目中强调是subsequence而不是substring，说明有序性的重要性。
本题要我们找到一个subsequence没有重复的character
2.确定Input/Output
Input: 一个字符串s
Output: 一个integer，表示最长subsequence的长度
3.选用数据结构
我们这里肯定要用到引用数据类型，这是毋庸置疑的。
如果直接考虑存储这个字符串的所有信息，我们需要一个tree，或者graph（如果考虑环的存在，但显然用graph是不明智的）
如果只考虑截断字符串的规则，我们需要一个字母和index对应的数据结构，key-value pair == dictionary
Solution 1: 选用字典
class Solution(object):
def lengthOfLongestSubstring(self, s):
prev = 0
ans = 0
dict = {}
for i,j in enumerate(s):
if j not in dict:
dict[j] = i
else:
# 保证prev是不重复字符串的前端
prev = max(dict[j] + 1, prev)
dict[j] = i
# 保证ans在字符串末尾得到更新
ans = max(ans, i + 1 - prev)
return ans
评价：这个解法使用了dictionary,巧妙地利用了dictionary无序不重复以及key, value都可赋值的特性。
思路分析：
字典的key用于存放一个值，value用于存放另一个相关值。
具体到这道题，由于没有重复的字符，那么重复的字符代表我们需要对sequence进行切割。
而我们面临的第二个问题是：单纯的根据某个字符串进行切割是不全面的
如对于 abac, 如果我们只考虑对a进行切割，那么只能得到ab或者ac，最后返回2
但实际上，我们可以切割出bac，这种情况下需要我们考虑对b进行切割。
如果你有一定的编程熟练度和逻辑思考能力，那么可以轻易地分析出这个问题可以抽象成参数不同的对单个字符的切割字符串的问题（即多个参数的简单函数）
对于这种情况，我们可以选择牺牲时间或者空间。
对于字符串这种非常小的数据，显然多用一些空间是更划算的。（即：对每个不同的char进行存储）
这道题中我们选择了dictionary用来存储各个字符是否出现过的信息。
Solution2: 选用Tree
使用Tree的思路更加清晰。
我们可以对任意的字符串画出一个Tree，依照如下例子的规则。
举几个例子：
如abcbcacb, 我们可以画出:
image
-
a-b-c
-
b 已存在, 另起一支
-
b-c-a
-
c 已存在, 另起一支
-
c-b
由于我们已经得到了几何化的tree，最终我们可以得到abc或者bca是最长路径，结果为3.
如 abcbcd, 我们可以画出：
image
-
a-b-c
-
b 已存在，另起一支
-
b-c-d
如此这般，问题就转化为了Tree的最大深度问题。
由于在网吧敲键盘很不爽所以略，之后github贴C语言ADT实现代码。
由于是作为recap而写，就不用连内存都不需要管的python了。
Tree相关的方法全是靠recursion来写，之后补上recursion的经典例子作为补充链接。
网友评论