专栏首页JackeyGao的博客Leetcode 算法 -3. Longest Substring Without Repeating Characters

Leetcode 算法 -3. Longest Substring Without Repeating Characters

Leetcode 算法 -3. Longest Substring Without Repeating Characters

Posted August 17, 2016

问题链接: 3. Longest Substring Without Repeating Characters 问题描述: Given a string, find the length of the longest substring without repeating characters. Examples: Given abcabcbb, the answer is abc, which the length is 3. Given bbbbb, the answer is b, with the length of 1. Given pwwkew, the answer is wke, with the length of 3. Note that the answer must be a substring, pwke is a subsequence and not a substring. 使用语言: Python

此题有点饶, 需要一组hash表记录字符的索引.

我们以ababcbb为例说明, 这里hash表的值-1是初始值, 这样在方便做+1操作. index 作为开始索引值, 起初index为0, 这是理所当然的。当遍历到第二个a index就成了2了, 同时把ab重置为初始值. maxlen为一个刷新最高值的变量. 通过当前索引 - index + 1计算(当再次迭代到c的时候, 此时i为4, index为2, 则: 4-2+1=3 ). 每次比上一次maxlen大的时候更新此值. 保证max_len是最大的.

重置hash表初始值的逻辑是:

  • 当此字符在hash表中的值不是-1(即不是初始值)
  • 此字符之前的所有字符hash表的值都会重置(比如上面遍历到第二个a是 0-2之间的ab都重置了 )
  • 在重置之前的字符索引值的时候把index增加到当前索引位置数.

刷新max_len逻辑

  • 当此字符在hash表中的值是-1
  • 计算公式: 当前索引 - index + 1

Python

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """

        index = 0
        max_len = 0
        d = {}

        for i in s:
            d[i] = -1

        for i in range(len(s)):
            # 重置hash表初始值的逻辑
            # 当此字符在hash表中的值不是-1
            if d[s[i]] != -1:
                while index <= d[s[i]]:
                    #此字符之前的所有字符hash表的值都会重置 
                    d[s[index]] = -1

                    #在重置之前的字符索引值的时候把index增加到当前索引位置数.
                    index += 1

            # 刷新max逻辑
            if i - index + 1 > max_len:
                max_len = i - index + 1

            d[s[i]] = i

        return max_len

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 日历小程序开发感想

    2018年, 年最末的时候, 终于把诗词周历小程序做出来并上线了。 本来已没有打算(考虑到审核比较麻烦, 可能还需要备案等很多流程。), 事情起因是在一次询问小...

    用户1416054
  • Django 自定义管理命令

    Django 提供了一组非常实用的命令, 可以通过django-admin.py和pytohn manage.py脚本调用. 关于这个Management Co...

    用户1416054
  • 一个Python3和Python2的range差异

    Python 3 中执行100000000 in range(100000001)会比Python 2快的非常多。

    用户1416054
  • 通配符与正则

    通配符和正则表达式很容易混淆,首先二者所应用的对象是不同的,通配符主要是用在 Shell 命令中,比如 find 、 ls 、 cp 等,而正则是使用在文本过滤...

    zucchiniy
  • 艺术鬼才!Unicode 字符还能这么玩?

    上周的时候,朋友圈的直升飞机不知道为什么就火了,很多朋友开着各种花式飞机带着起飞。

    andyxh
  • Windows 程序的数据类型与 Character Set 设置

    即使学习 C 语言的开发者,在第一次接触 Windows 编程的时见到像 LPCTSTR、TCHAR 这样的类型时都会觉得很难理解。请不要害怕,接下来我会介绍 ...

    范蠡
  • 第五章 正则表达式&字符处理

    如:邮箱的书写格式为:XXXX@XXXX.XXX,此格式即为邮箱地址的正则表达式。

    晓天
  • C#常见转义字符

    ·一种特殊的字符常量; ·以反斜线"\"开头,后跟一个或几个字符。 ·具有特定的含义,不同于字符原有的意义,故称“转义”字符。 ·主要用来表示那些用一般...

    Dabelv
  • lombok插件

    IDE: IntelliJ IDEA  首先在设置的插件栏中安装lombok,然后使用如下的pom依赖: <dependency>    <groupId>or...

    用户1134788
  • MySQL学习小结

    黑泽君

扫码关注云+社区

领取腾讯云代金券