Java 122ms O(S*T), use Queue


  • 0

    If the object contains enough information, it is safe to use Queue to find next matched index of S and T. Though I don't like the code myself as it is not beautiful at all

        class Node{
            int startIdx;
            int curIdx;
            int depth;
            Node(int startIdx, int curIdx){
                this.startIdx = startIdx;
                this.curIdx = curIdx;
                depth = 0;
            }
        }
        
        public String minWindow(String s, String t) {
            if(s == null || t == null || s.length() < t.length()){
                return "";
            }
            
            int sLen = s.length();
            int tLen = t.length();
            
            char[] schs = s.toCharArray();
            char[] tchs = t.toCharArray();
            
            List<List<Integer>> map = new ArrayList<>();
            
            for(int i = 0; i < tLen; i++){
                List<Integer> list = new ArrayList<>();
                for(int j = 0; j < sLen; j++){
                    if(tchs[i] == schs[j]){
                        list.add(j);
                    }
                }
                if(list.size() == 0){
                    return "";
                }
                map.add(list);
            }
            
            Queue<Node> queue = new LinkedList<>();
            for(int idx : map.get(0)){
                queue.offer(new Node(idx, idx));
            }
            
            for(int i = 1; i < tLen; i++){
                List<Integer> list = map.get(i);
                if(queue.isEmpty()){
                    return "";
                }
                for(int idx : list){
                    Node node = null;
                    while(!queue.isEmpty() && queue.peek().curIdx < idx && queue.peek().depth != i){
                        node = queue.poll();
                    }
                    if(node != null){
                        node.curIdx = idx;
                        node.depth++;
                        queue.offer(node);
                    }
                }
                
                while(!queue.isEmpty() && queue.peek().depth != i){
                    queue.poll();
                }
            }
            
            String res = "";
            int min = Integer.MAX_VALUE;
            while(!queue.isEmpty()){
                Node node = queue.poll();
                if(node.curIdx - node.startIdx < min){
                    min = node.curIdx - node.startIdx;
                    res = s.substring(node.startIdx, node.curIdx + 1);
                }
            }
            
            return res;
        }
    

Log in to reply
 

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