Dowemo
0 0 0 0

In this type of blog, the time complexity analysis of each algorithm is the blogger itself. This type of blog is also the author 's own.
One, problem.
  • Input: a string s
  • Output: output its longest substring, which cannot contain the same character
  • Assuming that the character in the string is all ascii, the encoding value is between 0 128.
Two, input and output examples
  • Enter: abcaa"
  • Output: 3, because the longest substring is"abc""
Three, solution
The maximum substring must be contained between two repeating characters, or a substring between a character and a start or end is a substring. Therefore, in the time of, the of the characters must be repeated, and the length of the substring isn't repeated at this time, and the For a string traversal, the other part is the search current character in the word already trave &, the time complexity of the whole algorithm is the time complexity of n * search search.

Solution: use hash idea to store the characters that have already been trave & ed

solution: because the word characters in this topic are ascii characters, there are up to 128 characters to create an array with length 128, each
package com.happy.leetcode.p3;
public class LongestSubstringWithoutRepeatingCharactersV1 {
 public static void main(String[] args) {
 String s ="au";
 System.out.println(s);
 System.out.println(new LongestSubstringWithoutRepeatingCharactersV1().lengthOfLongestSubstring(s));
 }
 public int lengthOfLongestSubstring(String s) {
 if ("".equals(s.trim())) {
 return 0;
 }
 int[] characters = new int[128];
 int maxLength = 1;
 int currentLength = 0;
 int currentPos = -1;
 for (int i = 0; i <s.length(); i++) {
 int index = (int) s.charAt(i);
 if (characters[index]> 0 && characters[index]>currentPos) {
 currentLength = i - 1 - currentPos;
 currentPos = characters[index] - 1;
 if (maxLength <currentLength) {
 maxLength = currentLength;
 }
 }
 characters[index] = i + 1;
 }
 currentLength = s.length() - 1 - currentPos;
 if (maxLength <currentLength) {
 maxLength = currentLength;
 }
 return maxLength;
 }
}

time complexity analysis: N * 1, the time complexity is ( n )

【 】 isn't a general algorithm. Because of the limitation of hash algorithm, this algorithm is only for ascii codeword.

Solution 2: search for indexof function with java

solution: the indexof function can be used when searching, actually this function is actually to traverse every character, find

package com.happy.leetcode.p3;
public class LongestSubstringWithoutRepeatingCharactersV2 {
 public static void main(String[] args) {
 String s ="cddba";
 System.out.println(s);
 System.out.println(new LongestSubstringWithoutRepeatingCharactersV2().lengthOfLongestSubstring(s));
 }
 public int lengthOfLongestSubstring(String s) {
 if ("".equals(s.trim())) {
 return 0;
 }
 int maxLength = 1;
 int currentLength = 0;
 int currentPos = 0;
 for (int i = 0; i <s.length(); i++) {
 int index = s.indexOf(s.charAt(i), currentPos);
 if (index> = 0 && index <i) {
 currentLength = i - currentPos;
 currentPos = index + 1;
 if (maxLength <currentLength) {
 maxLength = currentLength;
 }
 }
 }
 currentLength = s.length() - currentPos;
 if (maxLength <currentLength) {
 maxLength = currentLength;
 }
 return maxLength;
 }
}
time complexity analysis: Indexof time complexity is n, so the total time complexity is ( n^2 )






Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs