public class MinDistance { public static void main(String[] args) { String str1 = "sailn"; String str2 = "failing"; int[][] dp = new int[str1.length()+1][str2.length()+1]; int dis = calculateDis(str1, str1.length(), str2, str2.length(), dp); display(dp,str1,str2); System.out.println("最短编辑距离为:"+dis); } public static int calculateDis(String str1,int index1,String str2,int index2,int[][] dp){ if(index1==0 && index2==0){ dp[index1][index2] = 0; return 0; } if(index1==0 && index2>0){ dp[index1][index2] = index2; return index2; } if(index1>0 && index2==0){ dp[index1][index2] = index1; return index1; } int t1 = calculateDis(str1, index1-1, str2, index2, dp)+1; int t2 = calculateDis(str1, index1, str2, index2-1, dp)+1; int t3 = calculateDis(str1, index1-1, str2, index2-1, dp); if(str1.charAt(index1-1)!=str2.charAt(index2-1)){ t3 = t3+1; } int result = min(t1,t2,t3); dp[index1][index2] = result; return result; } private static int min(int a,int b,int c){ return a<b?(a<c?a:c):(b<c?b:c); } private static void display(int[][] dp,String str1,String str2){ System.out.print("\t\t"); for(char a :str2.toCharArray()){ System.out.print(a+"\t"); } System.out.println(); int count = -1; for(int[] a : dp){ if(count>=0){ System.out.print(str1.charAt(count)); } System.out.print("\t"); for(int b:a){ System.out.print(b+"\t"); } System.out.println(); count++; } } }
相关推荐
总的来说,编辑距离算法是理解和实现的重要工具,它能够帮助我们处理字符串的相似度问题,提高用户体验,特别是在搜索、纠错和自动建议等功能中。在分析`test`文件中的具体实现时,我们可以更深入地了解这个算法如何...
若是最短编辑距离问题,涉及到字符插入、删除或替换,可以使用Levenshtein距离算法,通过构建二维动态规划矩阵来计算两个字符串之间的最小编辑距离。 在课程设计中,可能会包含以下内容: 1. **源码实现**:学生...
本题目是在传统编辑距离的基础上进行了一定程度的变化和扩展,要求求解从一个字符串到另一个字符串的最短路径,特别地,在字符串中的相应位置字符相同时,可以直接跳过中间的步骤。 #### 颢目描述 给定两个字符串A...
5. **动态规划**:背包问题、最长公共子序列、最短编辑距离等,通过存储和利用子问题的解来优化整体求解过程,适用于许多优化问题。 6. **字符串操作**:KMP算法、Rabin-Karp算法等,用于高效地进行字符串匹配,...
《2018JAVA经典教程:数据结构与算法经典问题解析》是一本深入探讨Java语言中数据结构和算法实现的教程。这本书旨在帮助读者理解并掌握如何使用Java有效地设计和解决各种计算问题。数据结构是计算机科学的基础,而算...
5. 字符串处理:Java中的字符串处理算法,如模式匹配(KMP算法、Boyer-Moore算法)、字符串反转、编辑距离等,是处理文本数据时不可或缺的工具。 6. 树结构:二叉树的遍历(前序、中序、后序遍历)、平衡二叉树...
10. **字符串处理**:如KMP算法、Rabin-Karp滚动哈希、Z算法等,用于模式匹配和字符串搜索。 11. **概率和统计**:在一些算法中,如蒙特卡洛方法和随机化算法,会用到概率和统计知识。 12. **机器学习和数据挖掘**...
3. 编辑距离:衡量两个字符串之间转换成对方所需的最少操作次数。 六、递归与回溯 1. 斐波那契数列:递归或迭代方式计算特定位置的斐波那契数。 2. N皇后问题:在N×N棋盘上放置皇后,使其互不攻击。 通过学习和...
总之,这个问题要求我们实现一个算法,根据上述逻辑计算两字符串之间的最短编辑距离。这个问题可以使用动态规划的方法来解决,通过构建一个二维数组并根据给定的递推规则填充数组,最终得到的结果就是两字符串的最短...
- 动态规划的基本思想,如背包问题、最长公共子序列、最小编辑距离等。 - 记忆化搜索,优化动态规划的时空复杂度。 4. **贪心算法**: - 贪心策略,如霍夫曼编码、Prim最小生成树、Kruskal算法等。 5. **回溯法...
Java算法大全是一个涵盖广泛、深度丰富的学习资源,包含近100种常见算法的源代码实现,对于希望提升自己在Java编程和算法设计能力的开发者来说,无疑是一份宝贵的参考资料。这份资料涉及到的数据结构和算法知识是...
本压缩包文件"java经典算法"很可能包含了一些基本到进阶的算法实现,这些算法是每一个Java程序员都应该熟悉和掌握的。 1. **排序算法**:排序是数据处理的基础,Java中常见的排序算法有冒泡排序、选择排序、插入...
7. **字符串处理**:包括KMP算法、Boyer-Moore算法、Rabin-Karp滚动哈希等字符串匹配算法,以及编辑距离计算等文本处理问题。 8. **贪心算法**:贪心算法在局部最优解的基础上寻找全局最优解,如霍夫曼编码、活动...
10. **字符串处理**:如KMP算法、Rabin-Karp滚动哈希、Boyer-Moore算法,这些都是高效处理字符串匹配问题的方法。 11. **数值计算**:包括快速傅里叶变换(FFT)、高精度计算等,这些算法在信号处理、图像分析等领域...
7. **字符串处理**:如模式匹配(KMP、Boyer-Moore等)、字符串排序、编辑距离等,这些在文本处理和自然语言处理中非常常见。 8. **数学算法**:包括素数检测、最大公约数、最小公倍数、矩阵运算等,它们在处理计算...
7. **字符串处理**:在Java面试中,字符串处理也是一个常见的话题,可能涉及到模式匹配(如KMP算法)、最长公共前缀、编辑距离等问题。 8. **递归与分治**:递归是解决问题的一种重要思想,如Fibonacci序列、快速幂...
3. **字符串与数组**:Java中的String类以及如何处理字符串操作,数组的声明、初始化和遍历。 4. **输入输出流**:I/O流的概念,如何进行文件读写操作,以及标准输入输出流的使用。 5. **集合框架**:ArrayList、...
7. **字符串处理**:KMP算法、Rabin-Karp算法或Boyer-Moore算法等,这些都是在字符串匹配问题中的高效解决方案。 8. **数据结构**:如链表、队列、栈、堆、图、树等。理解并能熟练运用各种数据结构,是解决复杂算法...
8. **字符串处理**:KMP算法、Rabin-Karp算法等用于模式匹配,还有编辑距离算法用于计算两个字符串之间的相似度。 源码包中的morecode.net可能是一个网站或项目的名称,这通常意味着它可能包含各种算法的实例代码和...