title: Best expression to evaluate from group of expressions to reach max score - Google Interview
body: <p>Given a match word say "bad" and list of words "bird", "cat", "mug", "thug", "irk", "kin", "in", "mad", "md"
  from the list of words try to form match word. each time you use  word in the given list you get a point. unmatched letters will carry negative points. so the goal is the maximize the points in this game.</p>
  
  <pre><code>"bad" = "bird" -&gt; "ir" + "a" + 1 point
  "ir" = "irk" - "k"           + 1 point 
  "k" = "kin" - "in"    + 1 point
  "in" = "in"           + 1 point
  "a" = -1 point
  </code></pre>
  
  <p>Total = 3 points.</p>
  
  <p>Find an algorithm(recursive possibly) to find the best possible score.</p>
  
  <p>I am lost to find out from the list of unevaluated expressions, to pick the best one to reach the optimal score. For example in the case above, if I evaluated "a" first instead of "ir" I would have got different result.  </p>
  
  <p>Planning to implement this way( I am sure LISP would do this in more cleaner way ) </p>
  
  <pre><code>int max_score = 0;
  </code></pre>
  
  <p>// To begin with expr_list contains one element i.e match_word</p>
  
  <pre><code>int get_score(node *word_list, node *expr_list, int recursion_depth) {
  
  int score = 0;
  node *left_expr, *right_expr;
  
  if(!word_list || recursion_depth &gt; 5) {
      return -list_size(expr_list);
  }
  else if (!expr_list) {
      return 0;
  }
  
  word_list = find_next_unvisted(word_list);
  while(expr_list) {
      while(word_list) {
          left_expr = elem_split_left(word_list, expr_list);
          right_expr = elem_split_right(word_list, expr_list);
          list_add(expr_list, left_expr);
          list_add(expr_list, right_expr);
          expr_list-&gt;visited = 1;
          word_list-&gt;visited = 1;
          prev_score = score;
          score++;
          score += get_score(find_next_unvisited(word_list), find_next_unvisited(expr_list), ++recursion_depth);
          if(score &gt; max_score) {
              max_score = score;
          }
          else { /* start backtracking */
              expr_list-&gt;visited = 0;
              word_list-&gt;visited = 0;
              // Undo elem split
              list_delete(expr_list, left_expr);
              list_delete(expr_list, right_expr);
              score = prev_score;
          }
          word_list = find_next_unvisted(word_list);
      }
      expr_list = find_next_unvisited(expr_list);
  }
  free_list(word_list);
  free_list(expr_list);
  return max_score;
  }
  </code></pre>