c - 从一组表达式中评估以达到最高分数的最佳表达式 - Google Interview

Question

给定一个匹配词“bad”和单词列表“bird”、“cat”、“mug”、“thug”、“irk”、“kin”、“in”、“mad”、“md” 从单词列表中尝试形成匹配词。每次您在给定列表中使用单词时，您都会得到一分。不匹配的字母将带有负分。所以目标是在这场比赛中获得最高分。

"bad" = "bird" -> "ir" + "a" + 1 point
"ir" = "irk" - "k"           + 1 point 
"k" = "kin" - "in"    + 1 point
"in" = "in"           + 1 point
"a" = -1 point

总计 = 3 分。

找到一个算法(可能是递归的)来找到最好的分数。

我迷失了从未评估的表达式列表中找出最佳表达式以达到最佳分数的方法。例如在上面的例子中，如果我先评估“a”而不是“ir”，我会得到不同的结果。

计划以这种方式实现(我相信 LISP 会以更简洁的方式做到这一点)

int max_score = 0;

//以 expr_list 开始包含一个元素，即 match_word

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 > 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->visited = 1;
        word_list->visited = 1;
        prev_score = score;
        score++;
        score += get_score(find_next_unvisited(word_list), find_next_unvisited(expr_list), ++recursion_depth);
        if(score > max_score) {
            max_score = score;
        }
        else { /* start backtracking */
            expr_list->visited = 0;
            word_list->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;
}

Answer 1

这一切都在一个 C 示例中:

http://en.wikipedia.org/wiki/Levenshtein_distance