文档章节

3. Longest Substring Without Repeating Characters

datacube
 datacube
发布于 2016/06/27 16:03
字数 786
阅读 12
收藏 0
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.*  

package com.lifeibigdata.algorithms.leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Created by lifei on 16/5/27.
 *
 *  时间复杂度为O(N)的算法
 使用i和j两个指针进行搜索,i代表候选的最长子串的开头,j代表候选的最长子串的结尾。
 先假设i不动,那么在理想的情况下,我们希望可以一直右移j,直到j到达原字符串的结尾,此时j-i就构成了一个候选的最长子串。每次都维护一个max_length,就可以选出最长子串了。
 实际情况是,不一定可以一直右移j,如果字符j已经重复出现过(假设i在位置k),就需要停止右移了。记录当前的候选子串并和max_length做比较。接下来为下一次搜寻做准备。
 在下一次搜寻中,i应该更新到k+1。这句话的意思是,用这个例子来理解,abcdef是个不重复的子串,abcdefc中(为了方便记录为abc1defc2),c1和c2重复了。
 那么下一次搜寻,应该跨过出现重复的地方进行,否则找出来的候选串依然有重复字符,且长度还不如上次的搜索。所以下一次搜索,直接从c1的下一个字符d开始进行,
 也就是说,下一次搜寻中,i应该更新到k+1
 */
public class LengthOfLongestSubstring {
    public static void main(String[] args) {
        LengthOfLongestSubstring lols = new LengthOfLongestSubstring();
        System.out.println(lols.lengthOfLongestSubstring("abcdefcgh"));

    }

    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; ++j) {
            i = Math.max(index[s.charAt(j)], i);//index['a']会将char转为ascII码,a是97
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;   //将j所在的值,的对应位置存到index数组中
        }
        return ans;
    }


//    public int lengthOfLongestSubstring(String s) {
//        int n = s.length();
//        Set<Character> set = new HashSet<>();
//        int ans = 0, i = 0, j = 0;
//        while (i < n && j < n) {
//            // try to extend the range [i, j]
//            if (!set.contains(s.charAt(j))){       //如果j没有出现重复字符,将j添加到set中,这个过程中,i保持不变
//                set.add(s.charAt(j++));
//                ans = Math.max(ans, j - i);        //比较获取最大的ans
//            }
//            else {                                 //出现重复字符,这个字符在i-j之间,所以从i开始逐个删除,直到不包含重复字符
//                set.remove(s.charAt(i++));
//            }
//        }
//        return ans;
//    }


//    public int lengthOfLongestSubstring(String s) {    //使用map存储字母和索引
//        int n = s.length(), ans = 0;
//        Map<Character, Integer> map = new HashMap<>(); // current index of character
//        // try to extend the range [i, j]
//        for (int j = 0, i = 0; j < n; ++j) {
//            if (map.containsKey(s.charAt(j))) {
//                i = Math.max(map.get(s.charAt(j)), i);
//            }
//            ans = Math.max(ans, j - i + 1);
//            map.put(s.charAt(j), j + 1);
//        }
//        return ans;
//    }


//    public int lengthOfLongestSubstring(String s) {
//        int n = s.length();
//        int ans = 0;
//        for (int i = 0; i < n; ++i)
//            for (int j = i + 1; j <= n; ++j)
//                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
//        return ans;
//    }
//
//    public boolean allUnique(String s, int start, int end) {
//        Set<Character> set = new HashSet<>();
//        for (int i = start; i < end; ++i) {
//            Character ch = s.charAt(i);
//            if (set.contains(ch)) return false;
//            set.add(ch);
//        }
//        return true;
//    }
}

© 著作权归作者所有

datacube
粉丝 9
博文 607
码字总数 152394
作品 0
海淀
程序员
私信 提问
Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", whic......

jdflyfly
2014/06/24
1K
0
LeetCode 003. Longest Substring Without Repeating

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", whic......

jzzlee
2015/05/20
19
0
Leetcode_3. Find the longest substring without repeating characters

3. Find the longest substring without repeating characters Given a string, find the length of the longest substring without repeating characters. 给一个字符串,求出最长的无重复字......

gexin1023
2018/06/27
0
0
最长非重复子字符串

原题   Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is......

一贱书生
2016/12/06
13
0
Leetcode3:最长不重复子串

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/Flying_sfeng/article/details/82854567 Leetcode3: Longest Substring Without Repeating Characters 具体题......

Flying_sfeng
03/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

领域驱动中的“贫血症和失忆症”

贫血症严重危害着人类健康,并且伴随有危险的副作用。当贫血领域对象被首次提出来时,它并不是一个博得赞美的词汇,它描述的是一个缺少内在行为领域对象。奇怪的是,人们对于贫血领域对象的态...

还仙
14分钟前
3
0
条码打印软件中标签预览正常打印无反应怎么解决

在使用条码打印软件制作标签时,有客户反馈,标签打印预览正常的,但是打印无反应,咨询是怎么回事?今天针对这个情况,可以参考以下方法进行解决。 一、预览正常情况下,打印没反应 (1)在条码...

中琅软件
24分钟前
3
0
判断字符串的时候

判断字符串的时候一定把常量房前边, //报警程度 String leve = vo.getDeviceAlertDeal().getWarnLevel(); if(("0").equals(leve)) { row.add("无报警"); }else if(("1").equals(leve)) { ro......

简小姐
24分钟前
5
0
Linux maven3.6.2 install

PS:安装 maven 之前请先安装 jdk 1.安装 wget 命令(安装过就不用了) yum -y install wget 2.寻找需要的 maven 版本 https://maven.apache.org/download.cgi 3.进入 /var/local 文件夹 cd...

东方神祇
26分钟前
4
0
Tomcat源码分析二:先看看Tomcat的整体架构

Tomcat源码分析二:先看看Tomcat的整体架构 Tomcat架构图 我们先来看一张比较经典的Tomcat架构图: 从这张图中,我们可以看出Tomcat中含有Server、Service、Connector、Container等组件,接下...

flygrk
29分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部