leetcode-algorithms-3 Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: 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.

解法1

一步步检查所有字串看是否有重复的字符

class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
string longest;
for (int i = 0; i < s.size(); ++i)
{
for (int j = s.size() - i; j > 0; --j)
{
string longesttemp = s.substr(i, j); bool repect = false;
int a[256] = {0};
for (int n = 0; n < longesttemp.size(); ++n)
{
int x = longesttemp[n];
++a[x];
if (a[x] > 1)
{
repect = true;
break;
}
}
if (!repect && (longesttemp.size() > longest.size())) longest = longesttemp;
}
}
return longest.size();
}
};

时间复杂度: O(n^3).

空间复杂度: O(min(n,m)).

解法2

解法1的时间复杂度太高了,效率低下.字符串查找要怎么提高效率,首先都应该想到Sliding Window算法.设定一个窗口[i, j],将i到j的内容存入map,下面滑动j,如果s[j] (s表示字符串)在map中存在,表示字符串已经重复了,记下最大值,然后将i窗口滑到s[j]上次的位置.

下面是代码的实现:

class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
int n = s.length();
std::unordered_map<char, int> m;
int len = 0; for (int i = 0, j = 0; j < n; ++j)
{
auto fiter = m.find(s[j]);
if (fiter != m.end())
{
i = (fiter->second) > i ? fiter->second : i;
} int temp_len = j - i + 1;
len = (len > temp_len) ? len : temp_len;
m[s[j]] = j + 1;
}
return len;
}
};

时间复杂度: O(n).只有一个j循环.

空间复杂度: O(m).m是最大的不重复子串的长度.

解法3

对于解法2有没更快捷的方式.参考KMP算法对字符串的处理,我们可以将字符存入整型数组,值存储字符所在的位置,这样就可以在算法2的基础上少一次查询.

class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
int n = s.length();
int len = 0;
int index[128] = {0}; for (int i = 0, j = 0; j < n; ++j)
{
i = i > index[s[j]] ? i : index[s[j]];
int temp_len = j - i + 1;
len = (len > temp_len) ? len : temp_len;
index[s[j]] = j + 1;
}
return len;
}
};

时间复杂度: O(n).

空间复杂度: O(128).

链接: leetcode-algorithms 目录

最新文章

  1. E - The Values You Can Make
  2. 关于启用 HTTPS 的一些经验分享(二)
  3. jQuery与Ajax的应用——《锋利的jQuery》(第2版)读书笔记3
  4. JavaScript一些函数
  5. DP:Miking Time(POJ 3616)
  6. Careercup - Google面试题 - 6283958983589888
  7. 【LeetCode】83 - Remove Duplicates from Sorted List
  8. java 连接数据库mysql的方法
  9. Map的内容按字母顺序排序
  10. [bzoj4151][AMPPZ2014]The Cave
  11. JSP运行过程 JSP脚本 静态动态包含 jsp指令 jsp内置对象jsp四大作用域 jsp动作元素 EL表达式 JSTL 设计模式 JSP开发模式 EL内置对象
  12. &lt;笔记&gt;Apache+PHP+MYSQL配置
  13. Linux主机操作系统加固规范
  14. python 字典的定义以及方法
  15. Pytorch Visdom
  16. 【读书笔记】iOS-访问iPod媒体库
  17. android应用私有存储文件的写入与读取-openFileInput 和 openFileOutput
  18. uchome 缓存生成
  19. 20155209林虹宇虚拟机的安装及一点Linux的学习
  20. hdu 4114 Disney&#39;s FastPass 状压dp

热门文章

  1. docker 安装redis
  2. Unity3D学习笔记(三十四):Shader着色器(1)
  3. [转载]undefined reference to `memcpy@GLIBC_2.14&#39;
  4. _battleground
  5. JaveWeb 公司项目(5)----- Java获取当前时间的年月日以及同Thrift格式的转化
  6. 用html+css+js实现选项卡切换效果
  7. curl: (6) Could not resolve host: www.baidu.com;
  8. 解决UnicodeEncodeError: &#39;gbk&#39; codec can&#39;t encode character u&#39;\u25aa&#39; in position 344 : illegal multiby
  9. Django与CSRF 、AJAX
  10. Token和SessionStorage(会话存储对象)