最长不重复子字符串问题(动态规划)

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

问题

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 subsequenceand not a substring.

分析

首先,这种题肯定不能暴力来解决,否则肯定会超时。所以,考虑用一个哈希表(Map<char, int>)来维护状态。key是字符,value是当前字符出现在字符串的位置。

可能有个疑问,为什么这道题归类到“动态规划”中。动态规划类题目中的一共特性就是要有一个状态转移方程,可是这道题直接看起来并没有。但其实,思想是相同通。即当前状态的解要根据之前上一状态的信息来求解。只不过求解的过程不能用一个状态转移方程来解决,所以我认为这道题也有着动态规划的思想。

时间复杂度

O(n)

代码

/**
 * https://leetcode.com/problems/longest-substring-without-repeating-characters/#/description
 *
 * dp
 */
#include <iostream>
#include <vector>
#include 
<map>
#include <string>

using namespace std;

#define MAX 1000000001

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char, int> dp; 
        int max_length = -1, cur_length = 0, cur_offset = 0, length = s.size(), last_offset = 0;
        for (int i = 1; i < length + 1; ++i) {
            map<char, int>::iterator it = dp.find(s[i - 1]);
            if (it != dp.end() && it->second >= cur_offset) {
                last_offset = it->second;
                cur_offset = last_offset + 1;
                cur_length = i - cur_offset + 1;
            } else {
                if (++cur_length > max_length) max_length = cur_length;
                dp.insert(pair<char, int>(s[i - 1], i));
            }   
            it->second = i;// re-write the current pos for the cur char
        }   
        return max_length > 0 ? max_length : 0;
    }   
};

int main(int argc, char * argv[]) {
    Solution * s = new Solution();
    cout<<s->lengthOfLongestSubstring("qwnfenpglqdq");
}

问题来源:https://leetcode.com/problems/longest-substring-without-repeating-characters/#/description


这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...

1 评论

发表评论

电子邮件地址不会被公开。