查找数组中单词之间的最小距离

Question

例:

WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the","quick","brown","fox","quick"));

断言(finder.distance("fox","the")== 3);

断言(finder.distance("quick","fox")== 1);

我有以下解决方案,似乎是O(n),但我不确定是否有更好的解决方案.有没有人有任何想法？

String targetString = "fox";
String targetString2 = "the";
double minDistance = Double.POSITIVE_INFINITY;
for(int x = 0; x < strings.length; x++){
    if(strings[x].equals(targetString)){
        for(int y = x; y < strings.length; y++){
            if(strings[y].equals(targetString2))
                if(minDistance > (y - x))
                    minDistance = y - x;
        }
        for(int y = x; y >=0; y--){
            if(strings[y].equals(targetString2))
                if(minDistance > (x - y))
                    minDistance = x - y;
        }
    }
}

Answer 1

解决方案是O(N^2)因为您在查找每个单词时遍历整个列表.首先,您找到第一个单词,然后再遍历整个列表以找到第二个单词.

您可以做的是使用两个变量来跟踪每个单词的位置,并通过list => 一次计算距离O(N).

int index1 = -1;
int index2 = -1;
int minDistance = Integer.MAX_VALUE;
int tempDistance = 0;

for (int x = 0; x < strings.length; x++) {
    if (strings[x].equals(targetString)) {
        index1 = x;
    }
    if (strings[x].equals(targetString2)) {
        index2 = x;
    }
    if (index1 != -1 && index2 != -1) { // both words have to be found
        tempDistance = (int) Math.abs(index2 - index1);
        if (tempDistance < minDistance) {
            minDistance = tempDistance;
        }
    }
}

System.out.println("Distance:\t" + minDistance);