当先锋百科网

首页 1 2 3 4 5 6 7

题目地址:

https://www.lintcode.com/problem/926/

给定一个长 n n n的字符串数组 A A A,再给定两个单词 w 1 w_1 w1 w 2 w_2 w2,问在 A A A里它们的最短距离。题目不保证 w 1 w_1 w1 w 2 w_2 w2不同,但保证它们都出现过。如果 w 1 = w 2 w_1=w_2 w1=w2,那么最短距离就定义为它们相邻的两次出现的最短距离。

开两个指针 i 1 i_1 i1 i 2 i_2 i2,分别指向两个单词相邻的两次出现。遍历 A A A,并维护两个指针的定义,关键在于 w 1 = w 2 w_1=w_2 w1=w2的情况,此时两个指针分别维护的是前一次出现和当前出现,所以要将 i 2 i_2 i2赋值给 i 1 i_1 i1,然后再将当前所处位置赋值给 i 2 i_2 i2。代码如下:

public class Solution {
    /**
     * @param words: a list of words
     * @param word1: a string
     * @param word2: a string
     * @return: the shortest distance between word1 and word2 in the list
     */
    public int shortestWordDistance(String[] words, String word1, String word2) {
        // Write your code here
        int res = Integer.MAX_VALUE, idx1 = -1, idx2 = -1;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                idx1 = i;
            }
            if (words[i].equals(word2)) {
                if (word1.equals(word2)) {
                    idx1 = idx2;
                }
                idx2 = i;
            }
            
            if (idx1 != -1 && idx2 != -1) {
                res = Math.min(res, Math.abs(idx1 - idx2));
            }
        }
        
        return res;
    }
}

时间复杂度 O ( n l ) O(nl) O(nl),空间 O ( 1 ) O(1) O(1) l l l是两个字符串的最长长度。