Why does my code have TLE?


  • 0
    M

    The logic of my code is correct. It passed many test cases. However there is always Time Limit Exception. I tested in Eclipse for the case where there's TLE and the correct result popped out almost immediately. I appreciate it if anybody could help get rid of the TLE. Thanks a lot.

    public class Solution {
        int size;
        String res;
        private class TrieNode {
            Map<Character, TrieNode> c = new HashMap<>();
            boolean isWord = false;
            String word = null;
            public TrieNode() {}
        }
        private class Trie {
            TrieNode root = new TrieNode();
            public Trie(String[] words) {
                for (String word : words) insert(word);
            }
            private void insert(String s) {
                TrieNode cur = root;
                for (char c : s.toCharArray()) {
                    if (!cur.c.containsKey(c)) cur.c.put(c, new TrieNode());
                    cur = cur.c.get(c);
                }
                cur.isWord = true;
                cur.word = s;
            }
        }
        public String minAbbreviation(String target, String[] dictionary) {
            if (target == null || dictionary == null) return "";
            if (dictionary.length == 0) return String.valueOf(target.length());
            size = target.length();
            res = target;
            Trie trie = new Trie(dictionary);
            dfs(target, 0, dictionary, new StringBuilder(), 0, 0, trie);
            return res;
        }
        
        private void dfs(String target, int ind, String[] dic, StringBuilder pre, int cnt, int l, Trie trie) {
            int len = pre.length();
            int l0 = l;
            if (ind == target.length()) {
                if (cnt > 0) {
                    pre.append(cnt);
                    ++l;
                }
                if (isValid(pre.toString(), trie.root, 0, 0) && l < size) {
                    res = pre.toString();
                    size = l;
                }
                pre.setLength(len);
                l = l0;
                return;
            }
            dfs(target, ind + 1, dic, pre, cnt + 1, l, trie);
            if (cnt > 0) {
                pre.append(cnt);
                ++l;
            }
            pre.append(target.charAt(ind));
            ++l;
            dfs(target, ind + 1, dic, pre, 0, l, trie);
            pre.setLength(len);
            l = l0;
        }
        
        private boolean isValid(String s, TrieNode node, int i, int times) {
            if (times == 0 && i == s.length()) return !node.isWord;
            if (times > 0) {
                for (TrieNode next : node.c.values()) {
                    if (!isValid(s, next, i, times - 1)) return false;
                }
                return true;
            }
            char c = s.charAt(i);
            if (!Character.isDigit(c)) {
                if (!node.c.containsKey(c)) return true;
                return isValid(s, node.c.get(c), i + 1, 0);
            } else {
                String num = "";
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    num += s.charAt(i++);
                }
                int t = Integer.parseInt(num);
                return isValid(s, node, i, t);
            }
        }
        
    }
    

Log in to reply
 

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