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.
<?php
/**
* Created by PhpStorm.
* User: zhanglingyu
* Date: 2019-03-29
* Time: 17:53
*/
// 用最笨的方法实现的
// 736ms 尴尬
class Solution {
/**
* @param String $s
* @return Integer
*/
function lengthOfLongestSubstring($s) {
if ($s == '') {
return 0;
}
$len = strlen($s);
$maxLen = 1;
for ($i = 0; $i < $len ; $i++) {
$tmpArray = [$s[$i]];
for ($j = $i+1; $j < $len ; $j++) {
$word = $s[$j];
// 距离
$c = $j - $i;
// 当数组里存在相同的 退出当前循环
if (in_array($word, $tmpArray)) {
$maxLen = $maxLen > $c ? $maxLen : $c;
break;
} else {
array_push($tmpArray, $word);
}
// 最后一位 + 1
if ($j == $len - 1) {
$maxLen = $maxLen > $c ? $maxLen : ($c + 1);
}
}
}
return $maxLen;
}
}
class Test extends \PHPUnit\Framework\TestCase
{
/** @test */
public function testSolution()
{
$solution = new Solution();
$s1 = 'abcabcabb';
$s1Len = $solution->lengthOfLongestSubstring($s1);
$this->assertEquals($s1Len, 3);
$s2 = 'bbbbbb';
$this->assertEquals($solution->lengthOfLongestSubstring($s2), 1);
$s3 = 'pwwkew';
$this->assertEquals($solution->lengthOfLongestSubstring($s3), 3);
$s4 = "";
$this->assertEquals($solution->lengthOfLongestSubstring($s4), 0);
$s5 = "au";
$this->assertEquals($solution->lengthOfLongestSubstring($s5), 2);
$s6 = "cdd";
$this->assertEquals($solution->lengthOfLongestSubstring($s6), 2);
}
}
// 32ms
class Solution {
/**
* @param String $s
* @return Integer
*/
function lengthOfLongestSubstring($s) {
$size = strlen($s);
$max = 0;
$dict = array();
for ($i = 0, $start = 0, $max = 0; $i < $size; $i++) {
$char = $s[$i];
if (isset($dict[$char]) && $dict[$char] >= $start) {
$count = $i - $dict[$char];
if ($count > $max) $max = $count;
$start = $dict[$char] + 1;
} else {
$count = ($i + 1) - $start;
if ($count > $max) $max = $count;
}
$dict[$char] = $i;
}
return $max;
}
}
// 20ms
class Solution {
/**
* @param String $s
* @return Integer
*/
function lengthOfLongestSubstring($s) {
$return = 0;
$substring = '';
for ($i = 0; $i < strlen($s); $i++)
{
$pos = strpos($substring, $s[$i]);
if ($pos !== FALSE)
{
$count = strlen($substring);
$return = $count > $return ? $count : $return;
// 字符串向前移动一位
$substring = substr($substring, $pos + 1).$s[$i];
}
else
{
$substring .= $s[$i];
if ($i == strlen($s) - 1)
{
$count = strlen($substring);
$return = $count > $return ? $count : $return;
}
}
}
return $return;
}
}
// 使用PHP的例子思路
// 8ms
func lengthOfLongestSubstring(s string) int {
str := []byte(s)
ret := 0
var substring string
l := len(str)
for i := 0; i < l; i++ {
str := string(str[i])
pos := strings.Index(substring, str )
if pos != -1 {
count := len(substring)
if count > ret {
ret = count
}
// 移动
substring = substring[(pos+1):] + string(s[i])
} else {
substring += string(s[i])
if i == l-1 {
count := len(substring)
if count > ret {
ret = count
}
}
}
}
return ret
}
//4ms
// 一直没看太明白， 标记一下。。。。
func lengthOfLongestSubstring(s string) int {
maxLen, start := 0, 0
table := [128]int{}
for i, _ := range table {
table[i] = -1
}
for i, c := range s {
if table[c] >= start {
start = table[c] + 1
}
table[c] = i
maxLen = maxInt(maxLen, i - start + 1)
}
return maxLen
}
func maxInt(a, b int) int {
if a > b {
return a
}
return b
}
// 12ms
func lengthOfLongestSubstring(s string) int {
length := 0
max := 0
start := 0
m := map[byte]int{}
for i := 0; i < len(s); i++ {
if index, ok := m[s[i]]; ok {
if index < start {
length++
} else {
start = index+1
length = i - index
}
} else {
length++
}
m[s[i]] = i
if length > max {
max = length
}
}
return max
}
方法一一般是自己实现的方法，其他方式是在discuss中查找的更为优秀的方法，用作学习和借鉴。