LeetCode 3 — Longest Substring Without Repeating Characters （C++ Java Python）

题目：http://oj.leetcode.com/problems/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.

题目翻译：

给定一个字符串，找到最长无重复字符的子串的长度。例如，"abcabcbb"的最长无重复字符的子串为"abc”，它的长度为3。"bbbbb”的最长子串为"b”，长度为1。

分析：

注意特殊情况的考虑：

1 只有1个字符时，直接返回1

2 当到达字符串结尾时，要把此时的长度考虑进去

C++实现：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
  int length = s.length();
  if(length == 1)
  {
   return 1;
  }

  int longest = 0;
  int len = 0;
  string tmp;

  for(int i = 0; i < length; ++i)
  {
   if(longest > length - i)
   {
    break;
   }

   len = 0;
   for(int j = i + 1; j < length; ++j)
   {
    ++len;

    tmp = s.substr(i, j - i);  // !
    auto pos = tmp.find(s[j]);
    if(pos != string::npos)
    {
     i += pos;

     int k = j;
     while((++k < length) && (s[i + 1] == s[k]))
     {
      ++i;
     }

     if(longest < len)
     {
      longest = len;
     }

     break;
    }

    if(j == length -1)
    {
     longest = len + 1;
     break;
    }
   }
  }

  return longest;
    }
};

Java实现：

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
  int length = s.length();
  if (length == 1) {
   return 1;
  }

  int longest = 0;
  int len = 0;
  String tmp;

  for (int i = 0; i < length; ++i) {
   if (longest >= length - i) {  // (1)
    break;        // no need to go on
   }
   
   len = 0;
   for (int j = i + 1; j < length; ++j) {
    ++len;

    tmp = s.substring(i, j);
    int index = tmp.indexOf(s.charAt(j));
    if (index != -1) {
     i += index;
     // compare following items
     int k = j;  // in order to make it clear(works well without k)
     while ((++k < length) && (s.charAt(i + 1) == s.charAt(k))) {
      ++i;
     }

     if (longest < len) {
      longest = len;
     }

     break;
    }

    if (j == length - 1) {
     longest = len + 1;  // this is true because of (1)
     break;              // to make it clear, do like this: 
                   // if (longest < len + 1) longest = len + 1;
    }
   }
  }

  return longest;
 }
}

Python实现：

class Solution:
    # @return an integer
    def lengthOfLongestSubstring(self, s):
        length = len(s)
        if length == 1:
            return 1
        
        longest = 0
        lenOfSubstr = 0
        
        i = 0
        while i < length:
            if longest > length - i:
                break
            
            lenOfSubstr = 0
            for j in range(i + 1, length):
                lenOfSubstr += 1 
                
                tmp = s[i : j]
                index = tmp.find(s[j]) 
                if index != -1:
                    i += index
                    
                    k = j + 1
                    while (k < length) and (s[i + 1] == s[k]):
                        i += 1
                        k += 1
                    
                    if longest < lenOfSubstr:
                        longest = lenOfSubstr
                        
                    break
                
                if j == length - 1:
                    longest = lenOfSubstr + 1
                    break
                
            i += 1
                
        return longest

感谢阅读，欢迎评论！

LeetCode 3 — Longest Substring Without Repeating Characters （C++ Java Python）

浏览过的版块