def minDistance(word1: str, word2: str) -> int: """ 计算将word1转换为word2所需的最小操作次数（编辑距离）。 参数: word1: 原始字符串 word2: 目标字符串 返回: 最小操作次数（整数） """ m, n = len(word1), len(word2) # 如果其中一个字符串为空，直接返回另一个字符串的长度（全插入或全删除） if m * n == 0: return m + n # 创建DP表，dp[i][j]表示word1前i个字符转换为word2前j个字符的最小操作数 dp = [[0] * (n + 1) for _ in range(m + 1)] # 初始化边界条件 for i in range(m + 1): dp[i][0] = i # word1前i个字符转换为空字符串需要i次删除操作 for j in range(n + 1): dp[0][j] = j # 空字符串转换为word2前j个字符需要j次插入操作 # 填充DP表 for i in range(1, m + 1): for j in range(1, n + 1): if word1[i - 1] == word2[j - 1]: # 字符相同，不需要操作，继承前一状态的值 dp[i][j] = dp[i - 1][j - 1] else: # 字符不同，取插入、删除、替换三种操作的最小值加1 dp[i][j] = 1 + min( dp[i][j - 1], # 插入操作 dp[i - 1][j], # 删除操作 dp[i - 1][j - 1] # 替换操作 ) return dp[m][n]# 测试示例if __name__ == "__main__": # 示例1 word1_1, word2_1 = "horse", "ros" print(f"示例1: word1 = '{word1_1}', word2 = '{word2_1}'") print(f"输出: {minDistance(word1_1, word2_1)}") # 应输出3 # 示例2 word1_2, word2_2 = "intention", "execution" print(f"示例2: word1 = '{word1_2}', word2 = '{word2_2}'") print(f"输出: {minDistance(word1_2, word2_2)}") # 应输出5 # 边界情况测试 word1_3, word2_3 = "", "abc" print(f"边界测试1: word1 = '{word1_3}', word2 = '{word2_3}'") print(f"输出: {minDistance(word1_3, word2_3)}") # 应输出3 word1_4, word2_4 = "abc", "" print(f"边界测试2: word1 = '{word1_4}', word2 = '{word2_4}'") print(f"输出: {minDistance(word1_4, word2_4)}") # 应输出3
import unittestdef minDistance(word1: str, word2: str) -> int: """ 计算将word1转换为word2所需的最小操作次数（编辑距离）。 参数: word1: 原始字符串 word2: 目标字符串 返回: 最小操作次数（整数） """ m, n = len(word1), len(word2) # 如果其中一个字符串为空，直接返回另一个字符串的长度（全插入或全删除） if m * n == 0: return m + n # 创建DP表，dp[i][j]表示word1前i个字符转换为word2前j个字符的最小操作数 dp = [[0] * (n + 1) for _ in range(m + 1)] # 初始化边界条件 for i in range(m + 1): dp[i][0] = i # word1前i个字符转换为空字符串需要i次删除操作 for j in range(n + 1): dp[0][j] = j # 空字符串转换为word2前j个字符需要j次插入操作 # 填充DP表 for i in range(1, m + 1): for j in range(1, n + 1): if word1[i - 1] == word2[j - 1]: # 字符相同，不需要操作，继承前一状态的值 dp[i][j] = dp[i - 1][j - 1] else: # 字符不同，取插入、删除、替换三种操作的最小值加1 dp[i][j] = 1 + min( dp[i][j - 1], # 插入操作 dp[i - 1][j], # 删除操作 dp[i - 1][j - 1] # 替换操作 ) return dp[m][n]class TestMinDistance(unittest.TestCase): """测试编辑距离算法""" def test_leetcode_examples(self): """测试LeetCode官方示例""" # 示例1: horse -> ros self.assertEqual(minDistance("horse", "ros"), 3) # 示例2: intention -> execution self.assertEqual(minDistance("intention", "execution"), 5) def test_empty_strings(self): """测试空字符串""" self.assertEqual(minDistance("", ""), 0) # 两个空字符串 self.assertEqual(minDistance("", "abc"), 3) # word1为空，需要插入3个字符 self.assertEqual(minDistance("abc", ""), 3) # word2为空，需要删除3个字符 def test_identical_strings(self): """测试相同字符串""" self.assertEqual(minDistance("abc", "abc"), 0) # 完全相同，无需操作 self.assertEqual(minDistance("", ""), 0) # 两个空字符串 self.assertEqual(minDistance("hello", "hello"), 0) # 相同非空字符串 def test_single_character_changes(self): """测试单字符变化""" self.assertEqual(minDistance("a", "b"), 1) # 替换操作 self.assertEqual(minDistance("a", "ab"), 1) # 插入操作 self.assertEqual(minDistance("ab", "a"), 1) # 删除操作 def test_complete_transformation(self): """测试完全转换""" self.assertEqual(minDistance("abc", "def"), 3) # 全部替换 self.assertEqual(minDistance("abc", "abcdef"), 3) # 插入3个字符 self.assertEqual(minDistance("abcdef", "abc"), 3) # 删除3个字符 def test_dna_sequence_examples(self): """测试DNA序列示例（生物信息学应用）""" # DNA序列编辑距离测试[6,7,8](@ref) self.assertEqual(minDistance("AGT", "AGCT"), 1) # 插入一个碱基 self.assertEqual(minDistance("A", "T"), 1) # 替换一个碱基 self.assertEqual(minDistance("GGGG", "TTTT"), 4) # 替换所有碱基 def test_complex_scenarios(self): """测试复杂场景""" # 需要混合操作的情况 self.assertEqual(minDistance("kitten", "sitting"), 3) # 经典示例 self.assertEqual(minDistance("saturday", "sunday"), 3) # 另一个经典示例 # 包含特殊字符 self.assertEqual(minDistance("a!b@c", "!@c"), 2) # 删除操作 def test_algorithm_correctness(self): """验证算法正确性（多种情况对比）""" test_cases = [ # (word1, word2, expected, description) ("horse", "ros", 3, "LeetCode示例1"), ("intention", "execution", 5, "LeetCode示例2"), ("", "", 0, "两个空字符串"), ("abc", "abc", 0, "相同字符串"), ("a", "b", 1, "单字符替换"), ("kitten", "sitting", 3, "经典示例"), ("AGT", "AGCT", 1, "DNA序列插入"), ] for word1, word2, expected, description in test_cases: with self.subTest(word1=word1, word2=word2, description=description): actual = minDistance(word1, word2) self.assertEqual(actual, expected)class TestMinDistanceEdgeCases(unittest.TestCase): """测试边界情况""" def test_unicode_characters(self): """测试Unicode字符""" self.assertEqual(minDistance("中文", "中文"), 0) # 中文字符相同 self.assertEqual(minDistance("a", "中"), 1) # 中英文字符替换 def test_long_strings(self): """测试较长字符串""" # 创建较长的重复模式字符串 word1 = "abc" * 10 # "abcabcabc..." word2 = "ac" * 15 # "acacacac..." # 测试算法能否处理较长输入 result = minDistance(word1, word2) self.assertTrue(result >= 0) # 结果应为非负整数 def test_special_characters(self): """测试特殊字符""" self.assertEqual(minDistance("a!b@c#", "!@#"), 3) # 特殊字符处理 self.assertEqual(minDistance("a*b+c", "x*y+z"), 5) # 运算符字符def run_comprehensive_test_suite(): """运行全面测试并生成详细报告""" # 创建测试加载器 loader = unittest.TestLoader() # 创建测试套件 suite = unittest.TestSuite() suite.addTests(loader.loadTestsFromTestCase(TestMinDistance)) suite.addTests(loader.loadTestsFromTestCase(TestMinDistanceEdgeCases)) # 运行测试 runner = unittest.TextTestRunner(verbosity=2) result = runner.run(suite) # 生成测试报告 print("\n" + "="*60) print("编辑距离算法测试报告") print("="*60) print(f"运行测试数: {result.testsRun}") print(f"失败数: {len(result.failures)}") print(f"错误数: {len(result.errors)}") if result.wasSuccessful(): print("🎉 所有测试通过！算法实现正确。") # 显示关键测试用例验证 print("\n关键测试用例验证:") key_test_cases = [ ("horse", "ros", 3, "LeetCode示例1"), ("intention", "execution", 5, "LeetCode示例2"), ("", "", 0, "空字符串处理"), ("abc", "abc", 0, "相同字符串"), ("kitten", "sitting", 3, "经典示例"), ] for word1, word2, expected, description in key_test_cases: actual = minDistance(word1, word2) status = "✅" if actual == expected else "❌" print(f"{description:15} | 输入: '{word1}' -> '{word2}'") print(f"{'':15} | 输出: {actual} (期望: {expected}) {status}") print("-" * 50) else: print("❌ 有测试失败，请检查算法实现。") # 输出失败详情 for test, traceback in result.failures + result.errors: print(f"\n失败测试: {test}") print(f"错误信息:\n{traceback}") return result.wasSuccessful()if __name__ == '__main__': # 运行全面测试 success = run_comprehensive_test_suite() # 退出代码 exit(0 if success else 1)
