剑指offer——50最长不含重复字符和子字符串

题目:

  请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。假设字符串中只包含’a~z”的字符。例如,在字符串“arabcacfr"中,最长的不含重复字符的子字符串是“acfr”,长度为4。

题解:
  方法一:

    使用滑动窗口函数【借助string中的find函数】

  方法二:
    使用动态规划

  

 1 //方法一:使用移动窗口
 2 string getLenghtSubstr(const string &str)
 3 {
 4     if (str.length() < 2)return str;
 5     string res, temp;
 6     int L = 0, R = 1;
 7     res.assign(str.begin() + L, str.begin() + R);
 8     temp = res;
 9     while (R < str.length())
10     {
11         if (temp.find(str[R])!=-1)
12         {
13             res = res.length() >= temp.length() ? res : temp;
14             L = R;
15             temp = "";
16         }
17         temp += str[R];
18         R++;
19     }
20     return res.length() >= temp.length() ? res : temp;
21 }
22 
23 //方法二:使用动态规划
24 //与移动窗口函数类似,只不过是用数组代替了string.find
25 string DP(const string &str)
26 {
27     if (str.length() <= 1)return str;
28     vector<int>word(26, -1);
29     string curStr = "", maxStr = "";
30     //int curL = 0, maxL = 0;
31     for (int i = 0; i < str.length(); ++i)
32     {
33         int index = word[str[i] - a];
34         if (index<0 || i - index>curStr.length())//如果没出现过,或者出现的位置在我目前记录的子串的前面,那么第i个字母我可以添加
35             curStr += str[i];  //++curL
36         else //第i个字母重复在我目前记录的子串中
37         {
38             maxStr = curStr.length() > maxStr.length() ? curStr : maxStr;//先更新
39             //maxL = curL > maxL ? curL : maxL;
40             curStr += str[i];
41             curStr.erase(0, curStr.length() - (i - index));//删除重复节点
42             //curL = i-index;
43         }
44         word[str[i] - a] = i;
45     }
46     return curStr.length() > maxStr.length() ? curStr : maxStr;
47     //return curL > maxL? curL :maxL;
48 }
相关文章
相关标签/搜索