I am getting time out errors by the online judge but locally runs in less than a secon?


  • 0
    M

    I am not sure what I am doing wrong. This is my implementation based on the feedback for the other postings on this problem. On my local machine it run in less than a second but it times out on the online judge.

    Any hints welcome.

    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Set;

    /**
     *
     * @author mark
     */
    public class Solution {
    
      private String start, end;
        private ArrayList<String> dict;
        private ArrayList<String> dict2;    
        private char[] alphabet = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
        private boolean cont;
    
        public int ladderLength(String start, String end, HashSet<String> dict) {
            this.start = start;
            this.end = end;
            this.dict = new ArrayList(dict);
            this.dict2 = new ArrayList();
            return getShortestCount(start, 1);
        }
    
        private int getShortestCount(String current, int count) {
            Queue<String> queue = new LinkedList<String>();
            queue.add(current);
            while (!queue.isEmpty()) {
                Set<String> matches = generateMatches(queue.remove());
                if (matches.contains(end)){
                    count++;
                    return count;
                }
                queue.addAll(matches);
                dict2.addAll(matches);
                count++;
            }
            return 0;
        }
    
    
        private Set<String> generateMatches(String current) {
            Set<String> matches = new HashSet<String>();
            for (int i = 0; i < current.length(); i++) {
                char[] tmp = current.toCharArray();
                for (int j = 0; j < alphabet.length; j++) {
                    tmp[i] = alphabet[j];
                    String tmpStr = new String(tmp);
                    if (this.dict.contains(tmpStr) && 
                            !current.equals(tmpStr)
                            && !dict2.contains(tmpStr)) {
                        matches.add(new String(tmp));
                    }
                }
            }
            return matches;
        }
    }

  • 0
    G

    This is the implementation of the constructor you are using in line "this.dict = new ArrayList(dict);"
    As per the size of the test cases here, I think the reason that your solution is timing out is because too much time will be spend in copying element of hashSet to Array one by one for very large dictionary.

    May be you can try avoiding using this list conversion approach.

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

Log in to reply
 

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