Fast java solution 19ms beats 97% using indexOf


  • 3
    K

    My solution is very simple. Compare s with every words in dictionary using String.indexOf(). If matched, then compare size and lexicographical order with the candidate.

    public class Solution {
        public String findLongestWord(String s, List<String> d) {
            String longest=null;
            Iterator<String> itr=d.iterator();
            while(itr.hasNext()){
                String dd=itr.next();
                int start=-1;
                boolean flag=true;
                for(int i=0;i<dd.length();i++){
                    start=s.indexOf(dd.charAt(i),start+1);
                    if(start<0){
                        flag=false;
                        break;
                    }
                }
                if(!flag)   continue;
                if(longest==null)   longest=dd;
                else{
                    if(dd.length()>longest.length())    longest=dd;
                    if(dd.length()==longest.length()&&dd.compareTo(longest)<0)   longest=dd;
                }
            }
            return longest==null?"":longest;
        }
    }
    

  • 7

    For "very simple" you're making a few things rather complicated. Especially that iterator and that "flag" thing. The result default can also be simpler. And it might be faster (at least with certain test cases) to do the length checks first.

    Just a little rewrite:

    public String findLongestWord(String s, List<String> d) {
        String longest = "";
    words:
        for (String dd : d) {
            if (dd.length() < longest.length() ||
                dd.length() == longest.length() && dd.compareTo(longest) > 0)
                continue;
            int start = -1;
            for (int i = 0; i < dd.length(); i++){
                start = s.indexOf(dd.charAt(i), start + 1);
                if (start < 0)
                    continue words;
            }
            longest = dd;
        }
        return longest;
    }
    

    Bigger rewrite:

    public String findLongestWord(String s, List<String> d) {
        String longest = "";
        for (String word : d)
            if (isBetter(word, longest) && isSubsequence(word, s))
                longest = word;
        return longest;
    }
    
    private boolean isBetter(String a, String b) {
        return a.length() > b.length() ||
               a.length() == b.length() && a.compareTo(b) < 0;
    }
    
    private boolean isSubsequence(String a, String b) {
        int start = -1;
        for (int i = 0; i < a.length(); i++){
            start = b.indexOf(a.charAt(i), start + 1);
            if (start < 0)
                return false;
        }
        return true;
    }

  • 0
    K

    @StefanPochmann Thanks for point out. Your code is pretty elegant. BTW, the "continue words;" is like a goto style feature.. I used it rarely.
    And I have a question, why "indexOf" is faster than those "handmade" isSubsequence functions? Any idea?


  • 1

    @konglingfan Really not "goto style". But I almost never use it, either. In Python (my main language) there are better ways (like all(...) or for ... else ...), and in any language it's cleaner to just use such an isSubsequence helper function.

    The "handmade" ones are probably mostly slower because indexOf has direct access to the characters whereas charAt is an indirection that costs time.


  • 0
    O

    @StefanPochmann

    I have read the original code for String.indexOf. However I still cannot find a clue why that runs much faster than the highest voted solution so far. Could you please explain it more? Thank you.

    FYI, using indexOf is much fast than doing it this way:

    private boolean isSubseq(String str, String s) {
        int m = str.length(), n = s.length(), strPtr = 0;
        for (int i = 0; i < n; i++) {
            if (str.charAt(strPtr) == s.charAt(i)) {
                strPtr++;
                if (strPtr == m) {
                    return true;
                }
            }
        }
        return false;
    }

  • 0

    @odin said in Fast java solution 19ms beats 97% using indexOf:

    the original code for String.indexOf

    Can you post that here as well?


  • 0
    O

    @StefanPochmann

    Sorry that I don't know how to adjust the format.

    Parameters:
    ch a character (Unicode code point).
    fromIndex the index to start the search from.
    Returns:
    the index of the first occurrence of the character in the character sequence represented by this object that is greater than or equal to fromIndex, or -1 if the character does not occur.

    
    1532
    1533    public int indexOf(int ch, int fromIndex) {
    1534        final int max = value.length;
    1535        if (fromIndex < 0) {
    1536            fromIndex = 0;
    1537        } else if (fromIndex >= max) {
    1538            // Note: fromIndex might be near -1>>>1.
    1539            return -1;
    1540        }
    1541
    1542        if (ch < Character.MIN_SUPPLEMENTARY_CODE_POINT) {
    1543            // handle most cases here (ch is a BMP code point or a
    1544            // negative value (invalid code point))
    1545            final char[] value = this.value;
    1546            for (int i = fromIndex; i < max; i++) {
    1547                if (value[i] == ch) {
    1548                    return i;
    1549                }
    1550            }
    1551            return -1;
    1552        } else {
    1553            return indexOfSupplementary(ch, fromIndex);
    1554        }
    1555    }

  • 0

    @odin You can format simply like you're told. With three backticks ```. Not three single quotes '''. Please still edit that.

    Anyway... as I said and as that code shows, it can directly access the array value. Unlike your code, which accesses that array indirectly through the charAt method call.

    Also, for another problem @yixuanwang-start recently showed Java optimizations. Java's own methods can be more optimized, and in the linked material I saw that indexOf is even made "intrinsic" on at least some CPUs (using special CPU instructions, "STTNI instructions in SSE4.2").


  • 0
    Y
    This post is deleted!

  • 0
    O

    @StefanPochmann @yixuanwang-start

    Thanks for the detailed explanation.


  • 0
    Y
    This post is deleted!

  • 0

    @yixuanwang.start said in Fast java solution 19ms beats 97% using indexOf:

    I don't think it's that bad to use iterator, especially when the forEach is basically iterator implicitly

    I think

    for (String dd : d) {
    

    is a lot clearer than

    Iterator<String> itr = d.iterator();
    while (itr.hasNext()) {
        String dd = itr.next();
    

    and it also doesn't introduce that extra variable.

    sometimes when the class defined doesn't implement the iterator interface, the forEach method will throw the exception, but there's no iterator at first glance and people may get confused

    I think you're mistaken. List extends Collection which extends Iterable (not "iterator") which is documented as "Implementing this interface allows an object to be the target of the "for-each loop" statement".

    Another thing is that when we try to delete an item from list, the for each will throw the ConcurrentModificationException, but using iterator explicitly won't have the problem, this is a design issue for java

    I just tried it with an iterator:

    import java.util.*;
    
    public class Test {
        public static void main(String[] args) throws Exception {
            List<Integer> list = new ArrayList<>();
            for (int i=0; i<10; i++)
                list.add(i);
            Iterator<Integer> itr = list.iterator();
            while (itr.hasNext())
                list.remove(itr.next());
        }
    }
    

    It does throw a ConcurrentModificationException as well. Did you mean something else?

    from the time efficiency POV, iterator is faster than loop when dealing with LinkedList and others that don't have random access

    I don't believe that. Can you demonstrate it? And what does random access have to do with it?


  • 0
    Y
    This post is deleted!

  • 0

    @yixuanwang.start said in Fast java solution 19ms beats 97% using indexOf:

    about iterator remove part, this is what I mean

    Ah, right, of course. Yeah, itr.remove(); works.

    in java8 we don't have to explicitly call iterator to do that:

    collect.removeIf(str -> str.startsWith("a"))
    

    if we're using arraylist, the java8 way can mimimize the time complexity from O(n^2) to O(n)

    Nice. Didn't know that method yet, though then again, I'm not a Java guy :-)

    in the last part I was trying to compare the normal for loop vs. iterator(including enhanced for loop and forEach)

    Ah, you meant "normal loop". I thought you were comparing "iterator-loop" with "for-each-loop", as those were the ones we were discussing.

    enhanced for loop and forEach

    Aren't they the same thing?


  • 0
    Y
    This post is deleted!

  • 0

    @yixuanwang.start Right, earlier you called my loop "forEach", that confused me. I'm btw now watching the video you linked to and just saw the real forEach loop and also realized that's what you meant.

    Ha, pythonic Java code. Never :-). But yeah, Java does become nicer and nicer, closer to Python, and I don't hate it as much anymore as I used to.


Log in to reply
 

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