Why list.index return different value as dic[]?


  • 0
    X
    class Solution:
    # @return an integer
    def lengthOfLongestSubstring(self, s):
        maxstr = 0
        curstr = []
        curdic = {}      
        
        for c in s:
            
            if c in curdic:
                i = curstr.index(c)# accepted
                i = curdic[c] # wrong result
    
                for dc in curstr[0:i+1]:
                    curdic.pop(dc)
                del curstr[0:i+1]
            
            curstr.append(c)
            curdic[c] = len(curstr) - 1
            if len(curstr) > maxstr:
                maxstr = len(curstr)
            
                    
        return maxstr
    

    my code got pass if I do not use curdic, which is a dictionary.

    I think curdic has O(1) lookup speed, it should be more efficient then curstr.index(?)... actually it may

    not, because to use curdic, you need "i" times deletion

    #But anyway, my question is why my code can NOT get pass when I set i = curdic[c]?
    #Input: "whtaciohordtqkvwcsgspqo"
    #Output: 11
    #Expected: 12


  • 0
    F

    I'm not quite follow your code, could you explain a little bit more? For the efficiency, yes you need to do some deletions when you encounter a duplicate, but overall, for every character you only have to do this once. So the overall time complexity is O(n), so it is actually quite efficient,.


Log in to reply
 

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