b

bertking

V1

2022/04/18阅读:16主题:默认主题

关于编辑距离的题目

多试几次又有何妨,无论是恋爱或推理,今天或明天。

算法柯南
算法柯南

一. 单词距离问题

243. 最短单词距离

245. 最短单词距离 III


1 题目描述

给定一个字符串数组 wordDict 和两个已经存在于该数组中的字符串 word1 和 word2 。返回列表中这两个单词之间的最短距离。

示例 1:

输入: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"

输出: 3

示例 2:

输入: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"

输出: 1

2 解题思路

抽象模型
抽象模型

我们在一次遍历的过程中,获得两个目标单词的下标,然后计算其最小距离即可。

此题针对于word1和word2有两种情况:

  1. word1 != word2;
  2. word1和word2有可能相同;

3. 代码实现

3.1 针对word1 != word2的情况

public int shortestDistance(String[] wordsDict, String word1, String word2) {
        if(wordsDict == null || wordsDict.length == 0return 0;
        int i1 = -1;
        int i2 = -1;

        int minDistance = wordsDict.length;

        for(int i = 0; i < wordsDict.length; i++){
            if(word1.equals(wordsDict[i])){
                i1 = i;

                if(i2 != -1){
                    minDistance = Math.min(minDistance,i1-i2);
                }
            }

            if(word2.equals(wordsDict[i])){
                i2 = i;

                if(i1 != -1){
                    minDistance = Math.min(minDistance,i2-i1);
                }
            }
        }
        return minDistance;
    }

3.2 针对word1可能等于word2的情况

我们只需要要过滤掉两个index指向同一个单词的情况(否则距离会被计算为0)

public int shortestDistance(String[] wordsDict, String word1, String word2) {
        if(wordsDict == null || wordsDict.length == 0return 0;
        int i1 = -1;
        int i2 = -1;

        int minDistance = wordsDict.length;

        for(int i = 0; i < wordsDict.length; i++){
            if(word1.equals(wordsDict[i])){
                i1 = i;

                if(i2 != -1){
                    minDistance = Math.min(minDistance,i1-i2);
                }
            }

            if(word2.equals(wordsDict[i])){
                i2 = i;
                // 注意这里的判断:i1 != i2
                if(i1 != -1 && i1 != i2){
                    minDistance = Math.min(minDistance,i2-i1);
                }
            }
        }
        return minDistance;
    }

PS: Java中字符串比较用 equals() 方法。

分类:

后端

标签:

后端

作者介绍

b
bertking
V1