Java n*(k*log(k)) AC PriorityQueue solution, where k<=n and k close to n/26 by average.


  • 0

    The idea is to link each string's lexicographical biggest one first. At the same time, find the maximum char.
    From each maximum char, we can start a string and these k strings are then put into the PriorityQueue to compare their first char and then move to the next char.

    The time complexity is n*k*log(k), where k is the number of strings starting with maximum char. Therefore, the worst case will be n*n*log(n) if all the char in the given strings are all the same. However, by average, if there are only 26 possible characters, 'a' to 'z', in the strings, then k should close to n/26 initially. In addition, k should decrease by 1/26 after each loop until k==1. As a result, k*log(k) < n => n*k*log(k) < n*n.
    The space complexity is O(k) because the Node object stores the pointer of a linked string which is not an actual String object.

    public class Solution {
        String reverse(String str) {
            StringBuilder sb = new StringBuilder(str);
            return sb.reverse().toString();
        }
        class Node {
            String[] strs;
            int from, from_idx, cur, cur_idx;
            String fromStr, curStr;
            char cur_char;
            boolean started = false;
            Node(String[] strs, int from, int from_idx, String fromStr){
                this.strs = strs;
                this.from = from;
                this.from_idx = from_idx;
                this.fromStr = fromStr;
                cur = from;
                curStr = fromStr;
                cur_idx = from_idx;
                cur_char = curStr.charAt(cur_idx);
            }
            boolean next(){
                if (cur_idx==curStr.length()-1) {
                    cur_idx=0;
                    cur = cur+1 == strs.length ? 0 : cur+1;
                    curStr = cur == from ? fromStr : strs[cur]; 
                } else {
                    cur_idx++;
                }
                if (cur==from && cur_idx == from_idx && started) return false;
                cur_char = curStr.charAt(cur_idx);
                started = true;
                return true;
            }
        }
        class NodeComp implements Comparator<Node> {
            public int compare(Node n1, Node n2){
                return n2.cur_char - n1.cur_char;
            }
        }
        public String splitLoopedString(String[] strs) {
            if (strs==null || strs.length==0) return null;
            char maxChar = 'a';
            int len = strs.length;
            for (int i=0; i<strs.length; i++ ) {
                for (char c : strs[i].toCharArray() ) {
                    if (c > maxChar ) maxChar = c;
                    String rev = reverse(strs[i]);
                    if ( rev.compareTo( strs[i] ) > 0) strs[i] = rev;
                }
            }
            PriorityQueue<Node> queue = new PriorityQueue(1, new NodeComp());
            for (int i=0; i<strs.length; i++ ) {
                for (int j=0; j<strs[i].length(); j++) {
                    if (strs[i].charAt(j)== maxChar) {
                        queue.offer(new Node(strs, i, j, strs[i]));
                        queue.offer(new Node(strs, i, strs[i].length()-1-j, reverse(strs[i])));
                    }
                }
            }
            StringBuilder ret = new StringBuilder();
            while ( ! queue.isEmpty() ) {
                PriorityQueue<Node> tempQueue = new PriorityQueue(1, new NodeComp());
                char curChar = queue.peek().cur_char;
                ret.append(curChar);
                while (! queue.isEmpty() && curChar == queue.peek().cur_char ) {
                    Node curNode = queue.poll();
                    if (curNode.next()) tempQueue.offer(curNode);
                }
                queue = tempQueue;
            }
            return ret.toString();
        }
    }
    

Log in to reply
 

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