2015-06-03

LeetCode 3 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.

问题分析与思路

一开始看题的时候，我又错误的理解了题目的意思（汗(⊙﹏⊙)b，感觉我看题意会容易理解错），后来了看了别人的解释，觉得下面这张图来表示题意是最好不过的了。
不含重复字符的最长子串
从左往右扫描，当遇到重复字母时，以上一个重复字母的 index+1，作为新的搜索起始位置，直到最后一个字母，复杂度是 O(n)。

问题求解

C++的解决方案：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int length = 0;
        int index = 0;
        while (index < s.size()) {
            string subString = "";
            int i = 0;
            while ((index + i < s.size()) && subString.find(s[index + i]) == subString.npos) {
                subString += s[index + i];
                i++;
            }
            if (index + i < s.size()) {
                index += subString.find(s[index + i]);
            }
            if (subString.size() > length) {
                length = subString.size();
            }
            index++;
        }
        return length;
    }
};

从string s的第一个字符开始往后遍历，若这个字符没有在子串中出现，则加入子串，若出现过则从这个出现过的字符的后一个字符开始继续遍历，比较没有重复的子串的长度，获得最长的子串长度。
附上网上别人写的解决方案，整体的思路是差不多的，写法不太一样，感觉比较简洁，用了一个数组来记录每个字符上次出现的位置，我想了一下，如果出现了非a~z的字符，感觉这个写法就有一丢丢问题了。可以学习：

// 时间复杂度 O(n)，空间复杂度 O(1)
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        const int ASCII_MAX = 26;
        int last[ASCII_MAX]; // 记录字符上次出现过的位置
        int start = 0; // 记录当前子串的起始位置
        fill(last, last + ASCII_MAX, -1); // 0 也是有效位置，因此初始化为-1
        int max_len = 0;
        for (int i = 0; i < s.size(); i++) {
            if (last[s[i] - 'a'] >= start) {
                max_len = max(i - start, max_len);
                start = last[s[i] - 'a'] + 1;
            }
            last[s[i] - 'a'] = i;
        }
        return max((int)s.size() - start, max_len); // 别忘了最后一次，例如"abcd"
    }
};

Luvina

LeetCode 3 Longest Substring Without Repeating Characters

问题描述

问题分析与思路

问题求解

相关知识点总结

C++中string的用法

string的特性描述

string的子串

string类的查找函数