243. Shortest Word Distance
2024-04-14 09:57:51
题目：
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.
链接： http://leetcode.com/problemset/algorithms/
题解：
找两个单词在数组中的距离。这个题比较没有意义...就跟找两个字母的距离一样。乍看题目还以为是word ladder。设置两个变量，分别代表每个单词的lastIndex，之后就是判断和计算了。也可以用一个变量来记录。
Time Complexity - O(n)， Space Complexity - O(1)
public class Solution {
public int shortestDistance(String[] words, String word1, String word2) {
if(words == null || words.length == 0 || word1 == null || word2 == null)
return Integer.MAX_VALUE;
int minDistance = Integer.MAX_VALUE;
int word1Index = -1, word2Index = -2;
for(int i = 0; i < words.length; i++) {
if(words[i].equals(word1))
word1Index = i;
if(words[i].equals(word2))
word2Index = i;
if(word1Index >= 0 && word2Index >= 0)
minDistance = Math.min(minDistance, Math.abs(word1Index - word2Index));
}
return minDistance;
}
}
二刷：
使用两个变量存下 word1和word2在数组中的位置，然后进行计算。
Java:
Time Complexity - O(n)， Space Complexity - O(1)
public class Solution {
public int shortestDistance(String[] words, String word1, String word2) {
if (words == null || words.length < 2 || word1 == null || word2 == null) {
return Integer.MAX_VALUE;
}
int word1Pos = -1, word2Pos = -1, minDistance = Integer.MAX_VALUE;
for (int i = 0; i < words.length; i++) {
String curWord = words[i];
if (curWord.equals(word1) || curWord.equals(word2)) {
if (curWord.equals(word1)) {
word1Pos = i;
}
if (curWord.equals(word2)) {
word2Pos = i;
}
if (word1Pos >= 0 && word2Pos >= 0) {
minDistance = Math.min(minDistance, Math.abs(word1Pos - word2Pos));
}
}
}
return minDistance;
}
}
三刷：
Java:
public class Solution {
public int shortestDistance(String[] words, String word1, String word2) {
int minDist = Integer.MAX_VALUE;
int word1Idx = -1, word2Idx = -1;
for (int i = 0; i < words.length; i++) {
if (words[i].equals(word1)) {
word1Idx = i;
if (word2Idx >= 0) minDist = Math.min(minDist, i - word2Idx);
} else if (words[i].equals(word2)) {
word2Idx = i;
if (word1Idx >= 0) minDist = Math.min(minDist, i - word1Idx);
}
}
return minDist;
}
}
Reference:
最新文章
- ubuntu 远程开机
- MySQL（MariaDB）的 SSL 加密复制
- 无法找到类：java.lang.ClassNotFoundException: com.mysql.jdbc.driver
- Redis附加功能之Redis事务
- 描述cookie,sessionstroage,localstrage的区别
- python网络爬虫学习笔记
- ListBox之类控件的Item项显示对象的两个属性
- java指令重排序的问题
- OAuth2.0学习（1-6）授权方式3-密码模式（Resource Owner Password Credentials Grant）
- Ajax+jquery+jaso传输数据
- 解决 Vue 动态生成 el-checkbox 点击无法赋值问题
- javascript学习笔记二
- CentOS7 上以 RPM 包方式安装 Oracle 18c 单实例
- Buffer学习笔记.
- JUC知识点总结图
- python ddt 实现数据驱动一
- Read from socket failed: Connection reset by peer 问题
- Java String 学习
- 【BZOJ3771】Triple（生成函数，多项式运算）
- 如何定位 Node.js 的内存泄漏