[LeetCode] Shortest Word Distance

简介: Problem Description: Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

Problem Description:

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = "coding"word2 = "practice", return 3.
Given word1 = "makes"word2 = "coding", return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.


The naive idea is very easy. But could you solve it in one-pass? Well, the one-pass code (taken from here) is rewritten in C++ as follows.

 1 class Solution {
 2 public:
 3     int shortestDistance(vector<string>& words, string word1, string word2) {
 4         int n = words.size(), idx1 = -1, idx2 = -1, dist = INT_MAX;
 5         for (int i = 0; i < n; i++) {
 6             if (words[i] == word1) idx1 = i;
 7             else if (words[i] == word2) idx2 = i;
 8             if (idx1 != -1 && idx2 != -1)
 9                 dist = min(dist, abs(idx1 - idx2));
10         }
11         return dist;
12     }
13 };

 

目录
相关文章
LeetCode 318. Maximum Product of Word Lengths
给定一个字符串数组 words,找到 length(word[i]) * length(word[j]) 的最大值,并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词,返回 0。
81 0
LeetCode 318. Maximum Product of Word Lengths
LeetCode 290. Word Pattern
给定一种 pattern(模式) 和一个字符串 str ,判断 str 是否遵循相同的模式。 这里的遵循指完全匹配,例如, pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应模式。
51 0
LeetCode 290. Word Pattern
|
算法 索引
LeetCode 214. Shortest Palindrome
给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
94 0
LeetCode 214. Shortest Palindrome
LeetCode 212. Word Search II
给定一个二维网格 board 和一个字典中的单词列表 words,找出所有同时在二维网格和字典中出现的单词。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
82 0
LeetCode 212. Word Search II
|
索引
LeetCode 79. Word Search
给定一个2D板和一个单词,找出该单词是否存在于网格中。 该单词可以由顺序相邻的单元的字母构成,其中“相邻”单元是水平或垂直相邻的单元。 相同的字母单元格不得多次使用。
78 0
LeetCode 79. Word Search
|
数据库 C语言
LeetCode 72. Edit Distance
给定两个单词word1和word2,找到将word1转换为word2所需的最小操作数。 您对单词允许以下3个操作: 插入一个字符 删除一个字符 替换一个字符
73 0
LeetCode 72. Edit Distance
Leetcode-Easy 72. Edit Distance
Leetcode-Easy 72. Edit Distance
90 0
Leetcode-Easy 72. Edit Distance
Leetcode-Easy 461.Hamming Distance
Leetcode-Easy 461.Hamming Distance
114 0
Leetcode-Easy 461.Hamming Distance
LeetCode之Hamming Distance
LeetCode之Hamming Distance
124 0