你的位置:首页 > Java教程

[Java教程]No.003:Longest Substring Without Repeating Characters


题目:

Given a string, find the length of the longest substring without repeating characters.
Example:
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.

官方难度:

Medium

翻译:

给定一个字符串,找出最长子串,字串中无重复字符。

例子:

abcabcbb最长字串为abc,长度为3

bbbbb最长字串为b,长度为1

pwwkew最长字串是wke,长度为3

注意,结果必须是字串,如pwke就不是例子3中的最长字串

思路:

1.用一个变量存储最大值,从头开始遍历字符串,每次增加新元素,对旧元素做一次判断,之后比较最大值。

解题中可能遇到的困难:

1.遇到重复字符串的时候,需要重置比较字符串,而且不是清空,是长度为1的当前重复字符串。

2.因为只有当遇到重复字符串的时候,当前比较字符转的append()工作会停止,然后再与最长字符串比较,所以最长字符串在末尾的情况要特殊考虑。

解题代码:

 1 private static String method(String str) { 2     int maxLength = 0; 3     // 结果集 4     StringBuffer result = new StringBuffer(); 5     StringBuffer temp = new StringBuffer(); 6     String tempStr; 7     for (int i = 0; i < str.length(); i++) { 8       tempStr = str.substring(i, i + 1); 9       // 不存在重复10       if (!isExist(temp, tempStr)) {11         temp.append(tempStr);12       } else {13         // 遇到重复,比较最大长度14         if (temp.length() > maxLength) {15           // temp超过最大长度,保存结果16           maxLength = temp.length();17           result = temp;18         }19         // 无论超过与否,都要重置temp,temp的值是当前的判断到重复的字符串20         temp = new StringBuffer(tempStr);21         continue;22       }23       // 特殊情况考虑:最长字符串在原字符串尾部24       if (i == str.length() - 1) {25         if (temp.length() > maxLength) {26           // 最后一个,没必要给maxLength赋值了,虽然这个值错了27           result = temp;28         }29       }30     }31     return result.toString();32   }33 34   // 判断check字符,是否存在于sb字段中35   private static boolean isExist(StringBuffer sb, String check) {36     for (int i = 0; i < sb.length(); i++) {37       if (sb.substring(i, i + 1).equals(check)) {38         // true表示存在重复39         return true;40       }41     }42     return false;43   }

View Code

测试代码地址:

https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/medium/Q003.java

LeetCode题目地址:

https://leetcode.com/problems/longest-substring-without-repeating-characters/

PS:如有不正确或提高效率的方法,欢迎留言,谢谢!