Really simple Java one pass / linear time solution (guaranteed easy)


  • 0
    S

    Checking words in the dictionary against our target already requires O(mn) expected time, where m is the average length of words and n is the size of the dictionary. Therefore although it seems tempting to sort, it doesn't really improve the theoretical time complexity (if not making it worse, since if we care about the length of words, then each comparison in the sorting process actually takes O(m) on average).

    I suppose that's the same idea as that if you need to find the min/max in an array (satisfying certain conditions), you just need to go through it once and compare each one against the current optimal value so far, which takes constant space, by the way.

    public class Solution {
        public String findLongestWord(String s, List<String> d) {
            String l = "";
            for (String t: d)
                if (isSub(s, t) && t.length() >= l.length())
                    if (t.length() > l.length() || t.compareTo(l) < 0)
                        l = t;
            return l;
        }
        
        boolean isSub(String s, String t) {
            int j = 0;
            for (int i = 0; i < t.length(); i++)
                while (j == s.length() || t.charAt(i) != s.charAt(j++))
                    if (j == s.length())
                        return false;
            return true;
        }
    }
    

  • -1
    Z

    This is still O(nm), so it is inappropriate to state the time complicity to be linear.


  • 0
    Z

    Why down vote? can you please correct me if I was wrong?


  • 2

    @zhongyuan9817 O(nm) is linear in nm. And that's the size of the input, so it's quite natural and appropriate to use that.


  • 0
    Z

    @StefanPochmann Actually I read some posts after I see this answer like this one.

    http://cs.stackexchange.com/questions/9523/is-omn-considered-linear-or-quadratic-growth

    And now I am convinced this is linear, since it is about the input size. Make a lot of sense now. Thanks


Log in to reply
 

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