public class Solution {// Note: this solution is not accepted, I will update it later.
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) return 0;
int maxLen = 0, i = 0;
// for(int i = 0; i < s.length(); i ++){
StringBuffer uniqSubSB = new StringBuffer();
while(i < s.length()){
// if(uniqSubSB.length() != 0) uniqSubSB.delete(0, uniqSubSB.length());
if(checkRepeat(uniqSubSB,s.charAt(i)) < 0){
uniqSubSB.append(s.charAt(i));
i ++;
if(i == s.length()){// In the case where this index has meet the end of string
return Math.max(maxLen, uniqSubSB.length());
}
}
else{
maxLen = Math.max(maxLen, uniqSubSB.length());
uniqSubSB.delete(0, uniqSubSB.length());
i = s.lastIndexOf(String.valueOf(s.charAt(i)),i - 1) + 1;// start next search from the last "same" // char before (i -1)
}
}
return maxLen;
}
public int checkRepeat(StringBuffer uniqSubSB, char c){// The O(n^2) time might be due to this method,
if(uniqSubSB.length() == 0) return -1;
//String current = String.valueOf(s.charAt(i));
int idx = uniqSubSB.toString().indexOf(String.valueOf(c));
return idx;
}
}
UPDATE:
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) return 0;
int maxLen = 0, i = 0;
// for(int i = 0; i < s.length(); i ++){
StringBuffer uniqSubSB = new StringBuffer();
boolean[] checkAppear = new boolean[256];// Only 256 chars, so this array can store a flag indicating //whether the char has existed. Accelerate check speed.
Arrays.fill(checkAppear,false);
while(i < s.length()){
if(!checkAppear[s.charAt(i)]){// check
checkAppear[s.charAt(i)] = true;
uniqSubSB.append(s.charAt(i));
i ++;
if(i == s.length()){
return Math.max(maxLen, uniqSubSB.length());
}
}
else{
Arrays.fill(checkAppear,false);
maxLen = Math.max(maxLen, uniqSubSB.length());
uniqSubSB = new StringBuffer();
i = s.lastIndexOf(String.valueOf(s.charAt(i)),i - 1) + 1;
}
}
return maxLen;
}
}
Hello, welcome to Yizhe's Blog. I am Yizhe Liu, graduated from University of Arizona, with Master degree, major in Electrical and Computer Engineering. Actually, I am software guy. In my blog, many posts are about the Leetcode questions. I will post my ideas and implementations, which are accepted by Leetcode. If you have different opinions, please leave comment. I am happy to discuss with you. So lets start rocking them!!!
Tuesday, April 22, 2014
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment