`
shuiguaiQQ
  • 浏览: 14539 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
文章分类
社区版块
存档分类
最新评论

java实现字符串最短编辑距离算法

    博客分类:
  • Java
阅读更多
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`文件中的具体实现时,我们可以更深入地了解这个算法如何...

    LUT算法与数据结构--学校超市选址问题和最短字符串问题

    若是最短编辑距离问题,涉及到字符插入、删除或替换,可以使用Levenshtein距离算法,通过构建二维动态规划矩阵来计算两个字符串之间的最小编辑距离。 在课程设计中,可能会包含以下内容: 1. **源码实现**:学生...

    华为OD机试C卷- 两个字符串间的最短路径问题(Java & JS & Python & C).md-私信看全套OD代码及解

    本题目是在传统编辑距离的基础上进行了一定程度的变化和扩展,要求求解从一个字符串到另一个字符串的最短路径,特别地,在字符串中的相应位置字符相同时,可以直接跳过中间的步骤。 #### 颢目描述 给定两个字符串A...

    java算法140实例

    5. **动态规划**:背包问题、最长公共子序列、最短编辑距离等,通过存储和利用子问题的解来优化整体求解过程,适用于许多优化问题。 6. **字符串操作**:KMP算法、Rabin-Karp算法等,用于高效地进行字符串匹配,...

    2018JAVA经典教程:数据结构与算法经典问题解析-Java语言描述

    《2018JAVA经典教程:数据结构与算法经典问题解析》是一本深入探讨Java语言中数据结构和算法实现的教程。这本书旨在帮助读者理解并掌握如何使用Java有效地设计和解决各种计算问题。数据结构是计算机科学的基础,而算...

    java经典算法案例

    5. 字符串处理:Java中的字符串处理算法,如模式匹配(KMP算法、Boyer-Moore算法)、字符串反转、编辑距离等,是处理文本数据时不可或缺的工具。 6. 树结构:二叉树的遍历(前序、中序、后序遍历)、平衡二叉树...

    Java算法大全(近100种算法打包)

    10. **字符串处理**:如KMP算法、Rabin-Karp滚动哈希、Z算法等,用于模式匹配和字符串搜索。 11. **概率和统计**:在一些算法中,如蒙特卡洛方法和随机化算法,会用到概率和统计知识。 12. **机器学习和数据挖掘**...

    JAVA近百种算法大全

    3. 编辑距离:衡量两个字符串之间转换成对方所需的最少操作次数。 六、递归与回溯 1. 斐波那契数列:递归或迭代方式计算特定位置的斐波那契数。 2. N皇后问题:在N×N棋盘上放置皇后,使其互不攻击。 通过学习和...

    解题思路27

    总之,这个问题要求我们实现一个算法,根据上述逻辑计算两字符串之间的最短编辑距离。这个问题可以使用动态规划的方法来解决,通过构建一个二维数组并根据给定的递推规则填充数组,最终得到的结果就是两字符串的最短...

    整理收集Java算法编程文档

    - 动态规划的基本思想,如背包问题、最长公共子序列、最小编辑距离等。 - 记忆化搜索,优化动态规划的时空复杂度。 4. **贪心算法**: - 贪心策略,如霍夫曼编码、Prim最小生成树、Kruskal算法等。 5. **回溯法...

    java算法大全(含源码包)

    Java算法大全是一个涵盖广泛、深度丰富的学习资源,包含近100种常见算法的源代码实现,对于希望提升自己在Java编程和算法设计能力的开发者来说,无疑是一份宝贵的参考资料。这份资料涉及到的数据结构和算法知识是...

    java简单算法

    本压缩包文件"java经典算法"很可能包含了一些基本到进阶的算法实现,这些算法是每一个Java程序员都应该熟悉和掌握的。 1. **排序算法**:排序是数据处理的基础,Java中常见的排序算法有冒泡排序、选择排序、插入...

    算法 第4版-谢路云 译 Java描述 -完整版.pdf

    7. **字符串处理**:包括KMP算法、Boyer-Moore算法、Rabin-Karp滚动哈希等字符串匹配算法,以及编辑距离计算等文本处理问题。 8. **贪心算法**:贪心算法在局部最优解的基础上寻找全局最优解,如霍夫曼编码、活动...

    经典算法(java、c语言描述)

    10. **字符串处理**:如KMP算法、Rabin-Karp滚动哈希、Boyer-Moore算法,这些都是高效处理字符串匹配问题的方法。 11. **数值计算**:包括快速傅里叶变换(FFT)、高精度计算等,这些算法在信号处理、图像分析等领域...

    100个java经典算法

    7. **字符串处理**:如模式匹配(KMP、Boyer-Moore等)、字符串排序、编辑距离等,这些在文本处理和自然语言处理中非常常见。 8. **数学算法**:包括素数检测、最大公约数、最小公倍数、矩阵运算等,它们在处理计算...

    java算法源码包.rar

    7. **字符串处理**:在Java面试中,字符串处理也是一个常见的话题,可能涉及到模式匹配(如KMP算法)、最长公共前缀、编辑距离等问题。 8. **递归与分治**:递归是解决问题的一种重要思想,如Fibonacci序列、快速幂...

    Java基础,Java进阶,Java数据结构,十大算法

    3. **字符串与数组**:Java中的String类以及如何处理字符串操作,数组的声明、初始化和遍历。 4. **输入输出流**:I/O流的概念,如何进行文件读写操作,以及标准输入输出流的使用。 5. **集合框架**:ArrayList、...

    [Java类]JAVA经典算法40题

    7. **字符串处理**:KMP算法、Rabin-Karp算法或Boyer-Moore算法等,这些都是在字符串匹配问题中的高效解决方案。 8. **数据结构**:如链表、队列、栈、堆、图、树等。理解并能熟练运用各种数据结构,是解决复杂算法...

    Java算法大全源码包

    8. **字符串处理**:KMP算法、Rabin-Karp算法等用于模式匹配,还有编辑距离算法用于计算两个字符串之间的相似度。 源码包中的morecode.net可能是一个网站或项目的名称,这通常意味着它可能包含各种算法的实例代码和...

Global site tag (gtag.js) - Google Analytics