Codesprint Regex problem - generate a string that matches a regex in Scala

Regex.scala

import java.util.HashMap
import scala.collection.mutable.Set

object Solution {

  class Node (var isTerm: Boolean = false) {
    var children: HashMap[String, Array[Node]] = new HashMap[String, Array[Node]]()
  } 
  
  def splitTokens(regex: String) : (String, String, Char) = {
    var head: String = "";
    var tail: String = "";
    var op: Char = '\0'
    
    // Unwrap parens
    var flag = if (regex.charAt(0) == '(') 1 else 0
      
    // Try to find outer '|'
    var state:Int = 0
    for(i <- 0 until regex.size) {
      regex.charAt(i) match {
        case '(' => 
          state += 1
        case ')' => 
          state -= 1
          if (state == 0 && flag == 1) {
            if (i == regex.size - 1) {
              return splitTokens(regex.substring(1, regex.size - 1))
            } else {
              flag = 0
            }
            
          }
          
        case '|' => 
          if (state == 0) {
	          head = regex.substring(0, i)
	          tail = regex.substring(i+1)
	          return (head, tail, '|')
          }
        case  _ =>
      }
    }
    
    // If it starts with left paren
    
    state = 0
    if (regex.charAt(0) == '(') {
    	for(i <- 0 until regex.size) {
    	  regex.charAt(i) match {
	        case '(' => 
	          state += 1
	        case ')' => 
	          state -= 1
	          if (state == 0) {
	            op = regex.charAt(i+1)
	            if (op == '*' && (i+2) < regex.size) {
	              head = regex.substring(0, i+2)
	              tail = regex.substring(i+2)
	              return (head, tail, '\0')
	            } else if (op == '*' && (i+2) == regex.size) {
	              head = regex.substring(0, regex.size - 1)
	              return (head, "", '*')
	            } else {
	              head = regex.substring(0, i+1)
	              tail = regex.substring(i+1)
	              return (head, tail, '\0')
	            }
	          }
	        case _ => 
    	  }
    	}
    }
    
    if (regex.size == 2 && regex.charAt(1) == '*')
      return (regex.substring(0, 1), "", '*')
    else if (regex.charAt(1) == '*')
      return (regex.substring(0, 2), regex.substring(2), '\0')
    return (regex.substring(0, 1), regex.substring(1), '\0')
  }
  
  def buildRegex(left: Node, right: Node, path: String): Unit = {
    if (path.contains('|') || path.contains('(') || path.contains('*'))
    if (path.length() > 1) {
	    val (head, tail, op) = splitTokens(path)
      	left.children.remove(path)
	    op match {
	      case '|' =>
	      	left.children.put(head, Array(right))
	      	left.children.put(tail, Array(right))
	      	buildRegex(left, right, head)
	      	buildRegex(left, right, tail)
	      case '*' =>
	      	var nodeA = new Node()
	      	var nodeB = new Node()
	      	if (left.children.get("") != null)
		      	left.children.put("", (left.children.get("") ++ Array(nodeA, right)).distinct)
		    else
		      	left.children.put("", Array(nodeA, right))
	      	nodeA.children.put(head, Array(nodeB))
	      	nodeB.children.put("", Array(right))
	      	if (right.children.get("") != null)
		      	right.children.put("", (right.children.get("") :+ nodeA).distinct)
		    else
		      	right.children.put("", Array(nodeA))
	      	buildRegex(nodeA, nodeB, head)
	      case  _ =>
	        var node = new Node()
	        left.children.put(head, Array(node))
	        node.children.put(tail, Array(right)) 
	        buildRegex(left, node, head)
	        buildRegex(node, right, tail)
	    }
    }
  }
 
  def createGraph(regex:String): Node = {
    var left = new Node()
    var right = new Node(true)
    left.children.put(regex, Array(right))
    buildRegex(left, right, regex)
    left
  }
  
  def findString(regex:String, len: Int): String = {
    var start = createGraph(regex)
    var set = Set[(Node, String)]()
    def dfs(curr:Node, str:String): String = {
      if (set contains (curr, str)) return "NIL"
      set.add((curr, str))
      if (len == str.size && curr.isTerm) return str
      if (str.size > len) return "NIL"
      var res = "NIL"
      var iter = curr.children.keySet().iterator()
      var keys: Array[String] = Array()
      while(iter.hasNext()) {
        keys = keys :+ iter.next()
      }
      keys.sortWith(_.size > _.size)
      for (key <- keys) {
        for (node <- curr.children.get(key)) {
          val tmp = dfs(node, str+key)
          if (tmp != "NIL") 
            return tmp
        }
      }
      res
    }
    dfs(start, "")
  }
  
  
  def main(args: Array[String]): Unit = {
    val N = readInt()
    val re = readLine()
    println(findString(re, N))
  }

}