821. 字符的最短距离
题目：
输入字符串 s 和字母 c，已知 c 在 s 中出现过。
返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。
备注：两个下标 i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数
解答：
- 方法一：自己想的
时间复杂度：O(n)，空间复杂度：xx
主要逻辑：
遍历循环字符串，将字符串按照指定字符进行划分；对第一次/最后一次匹配到的单独处理
var shortestToChar = function(s, c) {
let res = [];
let ifFirst = true;
while(s.length > 0) {
let index = s.indexOf(c);
s = s.substring(index + 1,);
let nextIndex = s.indexOf(c);
// 当前 index 为 0
if (index === 0) {
res.push(0);
ifFirst = false;
continue
}
// 第一个匹配到的c
if(ifFirst) {
for(let i = index; i >= 0 ;i--) {
res.push(i);
}
ifFirst = false;
// 第一次 + c 为最后一位
if(!s) {
break
}
continue
}
// 中间
if (index !== -1) {
let mid = Math.ceil(index / 2);
let isOdd = index % 2;
for(let i = 1; i <= index; i++) {
if(i <= mid) {
res.push(i);
continue
}
// 奇偶数
if(isOdd) {
mid--;
isOdd = 0;
}
res.push(mid--);
}
res.push(0);
// 最后一个字母为 c 的情况
if (!s) {
break
}
continue
}
// 最后一个 c
for(let i = 1; i < index ; i++) {
res.push(i);
}
// c 后面还有内容
if (index === -1) {
for(let i = 1; i <= s.length ; i++) {
res.push(i);
}
}
break
}
return res
};
- 方法二：
时间复杂度：O(n)，空间复杂度：xx
核心逻辑：比较当前 i 与前后字符串位置的大小，取较小者为结果
var shortestToChar = (s,c) => {
let res = [];
let now = s.indexOf(c);
let prev = now;
for(let i = 0;i < s.length ; i++) {
now = s.indexOf(c, i);
if (i <= prev) {
res.push(now - i);
}
if (i > prev && i <= now) {
let dis = Math.min((now - i), (i - prev));
res.push(dis);
}
if (now === -1) {
res.push(i - prev);
}
if (i === now) {
prev = now;
}
}
return res
}