Leetcode 1255-递归与回溯

Question

我不太明白为什么当我们有第二个 for 循环来恢复 letterCount 时我们使用 .clone() 方法。当我在没有 .clone() 方法的情况下运行这段代码时，它给了我错误的答案？那么到底需要什么

public int solution(String[] words, int[] letterCount, int[] score, int ind) {
    if (ind == words.length)
        return 0;

    int sno = solution(words, letterCount.clone(), score, ind + 1); // Skip word

    String word = words[ind];
    int sword = 0;
    boolean flag = true;

    for (char ch : word.toCharArray()) {
        int letterIndex = ch - 'a';
        if (letterCount[letterIndex] == 0) {
            flag = false;
            break;
        }
        letterCount[letterIndex]--;
        sword += score[letterIndex];
    }

    int syes = 0;
    if (flag) 
        syes = sword + solution(words, letterCount, score, ind + 1); // Use word

    // Restore letterCount 
    for (char ch : word.toCharArray()) {
        letterCount[ch - 'a']++;
    }

    return Math.max(sno, syes);
}

}

Answer 1

你的回溯不起作用，因为当一个字母的计数下降到 0 时你就中断了，但是恢复计数的循环无条件地将所有字母添加回来。

如果删除

break

，那么您的代码无需克隆即可正常工作。

for (char ch : word.toCharArray()) {
    int letterIndex = ch - 'a';
    if (letterCount[letterIndex] == 0)
        flag = false;
    letterCount[letterIndex]--;
    sword += score[letterIndex];
}