胡说叔叔
这是一个动态规划问题。它们可以通过两种基本方式解决。一种是写一个递归函数，然后memoize。另一种是自底向上构建数据结构。自上而下的方法通常更容易编写。自下而上的方法通常更有效。这就是为什么两者都要学习的原因。我将在 Python 中演示自上而下的方法。考虑以下功能：def best_k_match_ending_at(string1, string2, k, i, j): if string1[i] != string2[j]: return (0, None, None) else: best = (0, None, None) for i_old in range(max(i-k, 0), i): for j_old in range(max(j-k, 0), j): this = best_k_match_ending_at(string1, string2, k, i_old, j_old) best = max(best, this) return (best[0] + 1, (i, best[1]), (j, best[2]))def best_k_match(string1, string2, k): best = (0, None, None) for i in range(len(string1)): for j in range(len(string2)): best = max(best, best_k_match_ending_at(string1, string2, k, i, j)) return best# prints (5, (5, (4, (3, (2, (1, None))))), (6, (5, (4, (3, (2, None)))))print(best_k_match('carpani', 'blarpan sharlie paneaui', 3))这是非常低效的。但正确。现在记忆它之前的一步。我喜欢重构以将辅助函数移动到主函数中。逻辑是一样的，但是当我记忆时，它会告诉我何时处理完数据。def best_k_match(string1, string2, k): def best_ending_at(i, j): if string1[i] != string2[j]: return (0, None, None) else: best = (0, None, None) for i_old in range(max(i-k, 0), i): for j_old in range(max(j-k, 0), j): this = best_ending_at(i_old, j_old) best = max(best, this) return (best[0] + 1, (i, best[1]), (j, best[2])) best = (0, None, None) for i in range(len(string1)): for j in range(len(string2)): best = max(best, best_ending_at(i, j)) return bestprint(best_k_match('carpani', 'blarpan sharlie paneaui', 3))现在我记住了def best_k_match(string1, string2, k): memoized = {} def best_ending_at(i, j): if string1[i] != string2[j]: return (0, None, None) elif (i, j) not in memoized: best = (0, None, None) for i_old in range(max(i-k, 0), i): for j_old in range(max(j-k, 0), j): this = best_ending_at(i_old, j_old) best = max(best, this) memoized[(i, j)] = (best[0] + 1, (i, best[1]), (j, best[2])) return memoized[(i, j)] best = (0, None, None) for i in range(len(string1)): for j in range(len(string2)): best = max(best, best_ending_at(i, j)) return bestprint(best_k_match('carpani', 'blarpan sharlie paneaui', 3))现在这很有效，但您可能不太喜欢输出。因为它是一个倒序的链表。这是一个更好的输出。def best_k_match(string1, string2, k): memoized = {} def best_ending_at(i, j): if string1[i] != string2[j]: return (0, None, None) elif (i, j) not in memoized: best = (0, None, None) for i_old in range(max(i-k, 0), i): for j_old in range(max(j-k, 0), j): this = best_ending_at(i_old, j_old) best = max(best, this) memoized[(i, j)] = (best[0] + 1, (i, best[1]), (j, best[2])) return memoized[(i, j)] best = (0, None, None) for i in range(len(string1)): for j in range(len(string2)): best = max(best, best_ending_at(i, j)) # Turn linked lists to something nicer. best_seq_rev = [] best_match_rev = [] best_link_1 = best[1] best_link_2 = best[2] while best_link_1 is not None: best_seq_rev.append(string1[best_link_1[0]]) best_match_rev.append((best_link_1[0], best_link_2[0])) best_link_1 = best_link_1[1] best_link_2 = best_link_2[1] best_seq = "".join(reversed(best_seq_rev)) best_match = list(reversed(best_match_rev)) return (best[0], best_seq, best_match)# prints (5, 'arpan', [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)])print(best_k_match('carpani', 'blarpan sharlie paneaui', 3))如果字符串的长度为n和m，则为O(n*m*k^2)。