【Day 2 】2021-05-11 - 821. 字符的最短距离
题目描述
入选理由
- 仍然是一道简单题，不过比昨天的题目难度增加一点
- 虽然这是一个字符串的题目，但其实字符串和数组没有本质差别，这在讲义中也提到了。
题目描述
给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。 示例 1: 输入: S = "loveleetcode", C = 'e' 输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0] 说明: - 字符串 S 的长度范围为 [1, 10000]。 - C 是一个单字符，且保证是字符串 S 里的字符。 - S 和 C 中的所有字母均为小写字母。
我的回答
https://github.com/leetcode-pp/91alg-3/issues/4#issuecomment-771297588
解法一
时空复杂度
时间复杂度：O(n^2)
空间复杂度: O(1)
两层遍历，第一层定位坐标，第二层向前向后分别找到一个相同的值后进行距离比较
/**
* @param {string} S
* @param {character} C
* @return {number[]}
*/
var shortestToChar = function (S, C) {
let res = []
for (let i = 0; i < S.length; i++) {
if (S[i] === C) {
res.push(0)
continue
}
let l = i; r = i; short = Infinity
while (l >= 0) {
if (S[l] === C) {
short = i - l
break
}
l--
}
while (r < S.length) {
if (S[r] === C) {
short = Math.min(short, r - i)
break
}
r++
}
res.push(short)
}
return res
};解法二
时间复杂度：O(n)
空间复杂度: O(1)
var shortestToChar = function (s, c) {
let res = []
let carry = - Infinity
for (let i = 0; i < s.length; i++) {
if (s[i] === c) carry = i
res[i] = Math.min(i - carry, res[i] || Infinity)
}
let orCarry = Infinity
for (let i = s.length - 1; i >= 0; i--) {
if (s[i] === c) orCarry = i
res[i] = Math.min(orCarry - i, res[i])
}
return res
};解法二
时空复杂度
时间复杂度：O(n)
空间复杂度: O(1)
从上面我们可以看出很多比较都是可以省略的，比如向前找到了以后，没遇到下一个相同字符串前都只需要加一即可,那我们就通过向前向后分别得出距离后比较
var shortestToChar = function (S, C) {
let arr = Array(S.length)
for (let i = 0; i < S.length; i++) {
if (S[i] === C) arr[i] = 0
else arr[i] = arr[i - 1] === void 0 ? Infinity : arr[i - 1] + 1
}
for (let i = S.length - 1; i >= 0; i--) {
if (arr[i] === Infinity || arr[i + 1] + 1 < arr[i]) arr[i] = arr[i + 1] + 1
}
return arr
};