C语言重构【821】字符的最短距离

秒速五厘米 2022-12-20 02:00 203阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个字符串 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 中的所有字母均为小写字母。

#### 方案： ####

*  根据C将S划分成一个一个小区域，每个区域正反赋值两遍，取小

class Solution
    { 
    public:
        vector<int> shortestToChar(string S, char C)
        { 
            int len = S.size();
            vector<int> nums(len, 10000);
            int tag = 0;
            for (int i = 0; i < len; i++)
            { 
                // 每找到一个，就向左推，直到上一个tag，或者距离大于nums数组
                if (S[i] == C)
                { 
                    for (int j = i; j >= tag; j--)
                    { 
                        if (nums[j] > i - j)
                        { 
                            nums[j] = i - j;
                        }
                        else
                            //遇到了比他小的则说明左侧有更近的，故不需要再继续
                            break;
                    }
                    tag = i;
                }
                else if (tag > 0 || S[0] == C)
                { 
                    //向右推进
                    nums[i] = i - tag;
                }
            }
            return nums;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode