【Lintcode】277. Word Spacing

题目地址：

https://www.lintcode.com/problem/word-spacing/description

给定一个长 n n n的字符串数组 A A A，给定两个字符串 s s s和 t t t，求它们在 A A A中的最小下标差（它们可能出现多次）。如果某个字符串不存在则返回 − 1 -1 −1。

思路是用两个变量分别记录最新发现的 s s s与 t t t的坐标，同时用坐标差的绝对值更新答案。代码如下：

import java.util.List;

public class Solution {
    /**
     * @param words: the words given.
     * @param wordA: the first word you need to find.
     * @param wordB: the second word you need to find.
     * @return: return the spacing of the closest wordA and wordB.
     */
    public int wordSpacing(List<String> words, String wordA, String wordB) {
        // write your code here.
        if (words == null || words.isEmpty()) {
            return -1;
        }
        
        int res = words.size(), posA = -1, posB = -1;
        for (int i = 0; i < words.size(); i++) {
            if (words.get(i).equals(wordA)) {
                posA = i;
            }
            if (words.get(i).equals(wordB)) {
                posB = i;
            }
            
            if (posA != -1 && posB != -1) {
                res = Math.min(res, Math.abs(posA - posB));
            }
        }
        
        return res == words.size() ? -1 : res;
    }
}

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