Longest Word In Dictionary Through Deletion


  • 0

    Click here to see the full article post


  • 0

    Why is sorting O(nlogn)? Is the worst case O(nlogn*x) when you have to compare s1 and s2 for n/2 times?


  • 0

    @zestypanda Yes, you are right. Updated. Thanks


  • 0
    Y

    isn't in place merge sort O(1) space?


  • 0
    R

    I do not think that your time complexities are correct. The isSubsequence method is O(m) where m is the size of the input string s. This means that the complexity overall should be O(n*m).


  • 0
    D

    I had a similar idea as #4 but my isSequence is wrong somehow (fails on #29), can anyone see what is wrong?

    int i = 0;
    for(char c : dict.toCharArray()) {
    while(s.charAt(i) != c) {
    if(++i == s.length()) {
    return false;
    }
    }
    }


  • 0
    D

    Nevermind, it'd fail on d of "bb" and s of "b"


  • 0
    P

    Can someone please tell me how the time complexity of sorted solution is O(nxlogn + nx) ? i thought it is O(nlogn + nx).


Log in to reply
 

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