Dowemo

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