首页 > 代码库 > Leetcode:Longest Substring Without Repeating Characters 解题报告
Leetcode:Longest Substring Without Repeating Characters 解题报告
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", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
SOLUTION 1:
http://blog.csdn.net/imabluefish/article/details/38662827
使用一个start来记录起始的index，判断在hash时 顺便判断一下那个重复的字母是不是在index之后。如果是，把start = map.get(c) + 1即可。并且即时更新
char的最后索引。
1 public class Solution { 2 public int lengthOfLongestSubstring(String s) { 3 if (s == null) { 4 return 0; 5 } 6 7 int max = 0; 8 HashMap<Character, Integer> map = new HashMap<Character, Integer>(); 9 10 int len = s.length();11 int l = 0;12 for (int r = 0; r < len; r++) {13 char c = s.charAt(r);14 15 if (map.containsKey(c) && map.get(c) >= l) {16 l = map.get(c) + 1;17 }18 19 // replace the last index of the character c.20 map.put(c, r);21 22 // replace the max value.23 max = Math.max(max, r - l + 1);24 }25 26 return max;27 }28 }
SOLUTION 2:
假定所有的字符都是ASCII 码，则我们可以使用数组来替代Map,代码更加简洁。
1 public int lengthOfLongestSubstring(String s) { 2 if (s == null) { 3 return 0; 4 } 5 6 int max = 0; 7 8 // suppose there are only ASCII code. 9 int[] lastIndex = new int[128];10 for (int i = 0; i < 128; i++) {11 lastIndex[i] = -1;12 }13 14 int len = s.length();15 int l = 0;16 for (int r = 0; r < len; r++) {17 char c = s.charAt(r);18 19 if (lastIndex[c] >= l) {20 l = lastIndex[c] + 1;21 }22 23 // replace the last index of the character c.24 lastIndex[c] = r;25 26 // replace the max value.27 max = Math.max(max, r - l + 1);28 }29 30 return max;31 }
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/string/LengthOfLongestSubstring.java
Leetcode:Longest Substring Without Repeating Characters 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。