educative.io

Heads-up: accept the answers regardlessly of the order of the words

Courses
,
#1

Good morning,
I have been wrapping my head around about how to resolve this exercise with iteration.
The reason for this is that for senior Java roles sometimes recursion gets rejected during interviews because in Java the JVM has preset limited space allocated to the stack and you can get stack overflow. Tail recursion optimization is not supported in Java.
Unfortunately, in your tests the result is not accepted just because of the different orders in which the words are spit out.
Could you please change this accordingly?
Thank you.

//TrieNode => {TrieNode[] children, boolean isEndWord, int value, 
//markAsLeaf(int val), unMarkAsLeaf()}
class TrieWords
{
  //Recursive Function to generate all words
  public static void getWords(TrieNode root, ArrayList < String > result, int level, char[] str) 
  {
    // use this as helper function
  }
  public static ArrayList < String > findWords(TrieNode root) 
  {
    ArrayList < String > result = new ArrayList < String > ();

    Deque<Pair> queue = new LinkedList<>();

    for (int i = 'a'; i < 'z'; i++) {
      TrieNode child = root.children[(char)(i - 'a')];
      if (child != null) {
        queue.offer(new Pair((char)(i), child, null));
      } 
    }
  
    while (!queue.isEmpty()) {
        Pair current = queue.poll();
        if (current.node.isEndWord) {
          Pair tail = current;
          String string = "";
          while(tail != null) {
            string += tail.value;   
            tail = tail.parent;
          }
           result.add(new StringBuilder(string).reverse().toString());   

        }

        for (int i = 'a'; i < 'z'; i++) {
          TrieNode child = current.node.children[(char)(i - 'a')];
          if (child != null) {
            queue.offer(new Pair((char)(i), child, current));
          } 
        }
    }
    return result;
  }


  public static class Pair {
    char value;
    TrieNode node;
    Pair parent;

    Pair(char value, TrieNode node, Pair parent) {
      this.value = value;
      this.parent = parent;
      this.node = node;
    }
  }  

}

Course: https://www.educative.io/collection/5642554087309312/5724822843686912
Lesson: https://www.educative.io/collection/page/5642554087309312/5724822843686912/5760131769827328