[C++]My solution using string operator only


  • 0
    Y

    Code first

    class Solution {
    public:
    int lengthOfLongestSubstring(string s) {
    	if (s.length() == 0) return 0;
    	string str=s.substr(0,1);                  //current longest substring
    	int max = str.length();                    // find the max length
    	for (int i = 1; i < s.length(); i++){
    		int pos = str.find_first_of(s[i]);     //return position if s[i] in str or -1 otherwise
    		str += s.substr(i,1);                         
    		if (pos>=0)
    			str = str.substr(pos+1, str.length()-pos); 
    		if (max < str.length())
    			max = str.length();
    	}
    	return max;
    }
    };
    

    My opinion, the time complexity rely on the input case. O(n) or O(n*n).

    Best case The elements in string are same, such that O(n) is enough.

    Worst case The characters in string are all unique, such that we need compare all characters before.
    Thus, the time complexity is O(n) orO(nlgn) using map that implement with binary tree.

    Finally, I'd like to say that how lucky you are who deal with the ascii character only.
    When it refer to Unicode string, you can not play int[256] trick or something like that again.

    I mean tens of thousand space can not be overlooked.

    Forgive me if I didn't make myself clear, and questions are welcome


  • 0
    V

    HI Echo-yang,If you dont mind can u tell why this is wrong .

    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            
        HashMap<Character,Integer>  map = new HashMap<Character,Integer>();
        if(s.length()==0) return 0;
        int len = s.length();
       
        int count =0;
        int max = 0;
        
        for(int i=0;i<len;i++)
         {
             if(!map.containsKey(s.charAt(i)))
             {   
                
             }
             else {
                 count = i-(map.get(s.charAt(i)));
                 
                 if(count>max) max = count;
                 map.clear();
            }
             map.put(s.charAt(i),i);
         }
         return max;
       }
    }

  • 0
    Y

    Since you did nothing when map.containsKey(s.charAt(I) is true. You should update the count as well, especially the worst case that every character are unique.

    Ooops, there is something more. Why you clear the map when character showed again.
    See this case: abcdcefg. Only c showed twice, The longest substring is dcefg. In your solution, d will miss.


  • 0
    N

    I heard from somewhere that string::the_first_of is of low efficiency, is that true? If so, why this is accpeted(I tried and it was accepted by OJ)?

    "Not only is the find_first_of STL algorithm much slower than the strpbrk C library function, but it also seems to have time complexity no better than O(N*M). "

    http://www.codeproject.com/Articles/18473/find-first-of-A-performance-pitfall-among-the-STL


  • 0
    Y

    You're right about this. However, in this very problem, maybe there're only 26 kinds of characters. Even the worst case, the time complexity is 13.5*n. (13.5=(26+1)*26/2/26)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.