Java: Queue of Stacks


  • 0
    V

    Obviously, not super-efficient, but, I think, a good use of standard library + fairly easy to understand.

    The idea:

    • Use a queue (first in, first out) to capture the order of words (should be preserved);
    • Use a stack (first in, last out) to capture the order of individual characters within the given word (should be reversed);

    Here's the implementation:

    public String reverseWords(String s) {
      // Stores all currently processed words
      Queue<Stack<Character>> contents = 
        new LinkedList<Stack<Character>>();
    
      // Points to the current word
      Stack<Character> cur = null;
    
      for (Character ch : s.toCharArray()) {
        if (!Character.isWhitespace(ch)) {
          // We're starting with the new word
          if (cur == null) {
            cur = new Stack<>();
            contents.add(cur);
          }
    
          cur.push(ch);
        } else {
          // We're done with the current word (encountered a whitespace)
          cur = null;
        }
      }
    
      StringBuilder sb = new StringBuilder();
    
      while (contents.size() > 0) {
        Stack<Character> item = contents.remove();
    
        // Making sure we don't put a whitespace in the beginning
        if (sb.length() > 0) {
          sb.append(" ");
        }
    
        while (item.size() > 0) {
          sb.append(item.pop());
        }
      }
    
      return sb.toString();
    }
    

    Runtime and space complexity is O(N).


Log in to reply
 

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