字符串中字符最短距离的JavaScript实现

资源摘要信息:"js代码-题目描述和解决方法" 1. 题目分析 题目要求我们编写一个JavaScript函数，该函数接受两个参数：一个字符串S和一个字符C。函数的目标是生成一个数组，其中每个元素表示字符串S中对应字符与字符C之间的最短距离。这里的距离是指字符在字符串中的位置差的绝对值。 2. 输入输出示例 给定输入字符串S = "loveleetcode"和字符C = 'e'，期望的输出数组是[3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]。数组中的每个数字对应字符串S中的一个字符，数字表示的是该字符与最近的'e'字符的距离。 3. 问题约束 - 字符串S的长度范围为[1, 10000]，表示输入的字符串可以非常长，需要考虑到算法的时间复杂度。 - C是一个单字符，且保证是字符串S里的字符，这意味着输入的字符C一定存在于字符串S中。 - 字符串S和C中的所有字母均为小写字母，说明我们不需要考虑大小写字母的区别。 4. 算法思路 要解决这个问题，我们可以采用以下思路： - 首先，我们可以在字符串S中找到所有字符C的位置，并将这些位置存放到一个数组中。 - 然后，对于字符串S中的每一个字符，我们需要找到它左侧最近的字符C的位置和右侧最近的字符C的位置，然后取两者之间的最小值作为该字符到字符C的最短距离。 - 我们可以使用双指针技术，一个指针从左到右遍历，一个指针从右到左遍历，这样可以分别计算左侧和右侧最近的字符C的位置。 5. JavaScript代码实现 根据上述思路，我们可以编写如下的JavaScript代码： ```javascript var shortestToChar = function(S, C) { let CPositions = []; for (let i = 0; i < S.length; i++) { if (S[i] === C) CPositions.push(i); } let result = []; let left = 0, right = CPositions.length - 1; for (let i = 0; i < S.length; i++) { if (left > right) { // 如果左侧指针已经超出了范围，说明所有字符C都在当前字符左侧， // 此时，只需要计算与最右侧字符C的距离 result.push(Math.abs(i - CPositions[right])); } else if (right < 0) { // 如果右侧指针已经超出了范围，说明所有字符C都在当前字符右侧， // 此时，只需要计算与最左侧字符C的距离 result.push(Math.abs(i - CPositions[left])); } else if (i - CPositions[left] < CPositions[right] - i) { // 否则，计算与左侧字符C的距离 result.push(Math.abs(i - CPositions[left])); left++; } else { // 计算与右侧字符C的距离 result.push(Math.abs(i - CPositions[right])); right--; } } return result; }; ``` 6. 算法复杂度分析 - 时间复杂度：我们只需要两次遍历字符串S，一次遍历字符C的位置数组，所以时间复杂度为O(n)，其中n是字符串S的长度。 - 空间复杂度：字符C的位置数组最大长度为n，因此空间复杂度为O(n)。 通过这种算法，我们可以高效地解决这个问题，即使对于较长的字符串S，也能在合理的时间内得到结果。