给定一个字符串, 请你找出其中不含有重复字符的 最长子串 的长度.
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc", 所以其长度为 3.
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b", 所以其长度为 1.
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke", 所以其长度为 3.
请注意, 你的答案必须是 子串 的长度,"pwke" 是一个子序列, 不是子串.
我的思路主要是利用双循环, 对其中的组合进行归类, 这种子字符串的组合不能含有重复的字母.
具体代码如下:
- public static int LengthOfLongestSubstring(string s)
- {
- if(string.IsNullOrEmpty(s))
- {
- return 0;
- }
- if(s.Length == 1)
- {
- return 1;
- }
- Dictionary<int, string> dic = new Dictionary<int, string>();
- int maxLength = 0;
- for (int i=0;i<s.Length - 1;i++)
- {
- if (!dic.Keys.Contains(i))
- {
- dic[i] = s[i].ToString();
- }
- for (int j=i+ 1;j<s.Length;j++)
- {
- if (!dic[i].Contains(s[j]))
- {
- string stmp = dic[i];
- stmp += s[j];
- dic[i] = stmp;
- }
- else
- {
- break;// 出现重复字母 break 掉
- }
- }
- if(dic[i].Length> maxLength )
- {
- maxLength = dic[i].Length;
- }
- }
- return maxLength;
- }
我的代码时间复杂度是 O(n^2)
来源: http://www.bubuko.com/infodetail-2968044.html