[算法分析与设计] leetcode 每周一题: 420. Strong Password Checker

题目链接: 

420. Strong Password Checker

题目大意:

给定一个代表密码的字符串 s, 只有当其同时满足以下 3个条件时才能视其为 "强密码":

1. 长度在区间 [6, 20] 内 (按字符计) ;

2. 至少分别包含 大写字母, 小写字母, 数字 各一个 ;

3. 任何连续的三个字符不完全相同 (比如: "..aaa.." 就不行, 而 "..aa.a.." 就可以) ;

现判断 s 是否是一个 "强密码", 若是, 返回 0 ; 若不是, 则返回 将 s 转换为一个 "强密码" 的最小 Levenshtein距离 ;

解题过程:

(1) 题意明显, ... 相对于算法题, 这题更像是业务逻辑处理 ... 包成个数据结构写起来会好看得多 ;

(2) 自然的思路便是 先对 s 做检查, 记录相关信息, 然后据此求出 最小编辑距离 ;

(3) 略麻烦的是 求最小编辑距离 的逻辑部分, 这里注意 插入字符操作 和 替换字符操作 对于 重复字符(条件3) 和 缺失字符(条件2) 来说没有太大区别 (显然这里不用考虑词频问题, 因为总会有 可以通过 被替换 的方式修正 条件2 的缺陷 的字符存在(要么是重复字符, 要么是多次出现的另一类必须字符, 要么是其他的无关字符, 注意长度必须 >= 6)), 此时对 n个连续重复字符 来说, 只需要做n / 3 次处理即可断开其连续重复 ; 而 删除字符 操作 则有所区别, 其只有 2个意义, 对 重复字符 的意义在于 ((3n - 1) / 3) - (3n / 3) = 1, 有效减少人口 ... ; 以及对 控制长度 的意义 ;

(4) 综合来看, 可以发现 不同的处理操作可以有不同的优先级, 这里我先进行 缩减长度的处理, 这时同时考虑不同长度的 连续重复字符 也有优先级 ; 另外还要考虑可复用的操作 ;

代码如下:

( 注: 代码略冗长, 可以进一步简化 .. )

class Solution {
public:
    int strongPasswordChecker(string s) {
        auto length = s.size();
        if (length == 0) { return 6; }
        
        map< size_t, size_t > repeats;

        bool lower = islower(s[0]);
        bool upper = isupper(s[0]);
        bool digit = isdigit(s[0]);
        for (size_t i = 1; i < length; i++) {
            if (s[i] == s[i-1]) {
                repeats[i-1] = 2;
            }

            auto c = s[i];
            if      ( isdigit( c ) ) { digit = true; }
            else if ( islower( c ) ) { lower = true; }
            else if ( isupper( c ) ) { upper = true; }
        }

        const size_t RepeatMerged = UINT_MAX;
        for (size_t i = length - 1; i > 0; i--) {
            auto index = i;
            if (repeats[index] > 0 && repeats[index-1] > 0) {
                repeats[index-1] += repeats[index] - 1;
                repeats[index] = RepeatMerged;
            }
        }

        vector< size_t > multisomes;
        for (auto r : repeats) {
            if (r.second >= 3 && r.second != RepeatMerged) {
                multisomes.push_back(r.first);
            }
        }
        auto sweepMultisomes = [&]() {
            multisomes.erase(
                remove_if(multisomes.begin(), multisomes.end(), [&](size_t i) { return repeats[i] < 3; }), multisomes.end()
            );
        };

        size_t ret = 0;

        if (length > 20) {
            auto d = length - 20;
            ret += d;

            for (auto i : multisomes) {
                auto & r = repeats[i];
                while ( d > 0 && r % 3 == 0 ) {
                    r--; length--;
                    d--;
                }
            }
            sweepMultisomes();

            for (auto i : multisomes) {
                auto & r = repeats[i];
                while ( d >= 2 && r % 3 == 1 ) {
                    r -= 2; length -= 2;
                    d -= 2;
                }
            }
            sweepMultisomes();

            for (auto i : multisomes) {
                if (d == 0) { break; }

                auto & r = repeats[i];
                auto dr = min( d, r - (3 - 1) );
                r -= dr; length -= dr;
                d -= dr;
            }
            sweepMultisomes();

        }

        size_t x = 0;
        if (!lower) { x++; }
        if (!upper) { x++; }
        if (!digit) { x++; }

        if (length < 6) {
            x = max(x, 6 - length);
        }

        size_t y = 0;
        for (auto i : multisomes) {
            y += repeats[i] / 3;
        }

        ret += max(x, y);
        return ret;
    }
};

Runtime: 0 ms