|
一个强密码应满足以下所有条件：
由至少6个，至多20个字符组成。
至少包含一个小写字母，一个大写字母，和一个数字。
同一字符不能连续出现三次 (比如 “…aaa…” 是不允许的, 但是 “…aa…a…” 是可以的)。
编写函数 strongPasswordChecker(s)，s 代表输入字符串，如果 s 已经符合强密码条件，则返回0；否则返回要将 s 修改为满足强密码条件的字符串所需要进行修改的最小步数。
插入、删除、替换任一字符都算作一次修改。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/strong-password-checker
解题思路：
任何一次操作都算一次修改，最终要返回修改s的最小步数。
首先从合格的密码要求看，有三个：
① 字符串长度大等于6且小于等于20；
② 有三种类型的字符；
③ 不能出现三个相同的字符。
假设字符长度为n，字符串包含字符类型为k。接下来分情况讨论
- n<=5时
此时，对字符串进行调整（插入、删除、替换）时，需要考虑n和k。
当字符串长度小于等于4时，需要考虑插入的次数 (6-n) 和缺失的字符类型 (3-k) 。如果存在情况③，不影响插入的次数，只影响插入的位置。所以只需要看s = max( (6-n) , (3-k) )。
当字符串长度等于5时，只需要进行一次插入操作，此时需要考虑缺失类型 (3-k) ，若k=1,则需要替换一次，插入一次；若k=2,则只需要插入一次。即为s = max( (6-n) , (3-k) )。 - 6<=n<=20时
此时，字符串已满足条件①，现在需要考虑k和替换重复字符。假设替换次数为p。
当k=1时，字符串仅包含一种字符，此时对每三个字符串进行一次替换，n/3。又n>=6,所以最后的只考虑替换次数s = p即可。
当k=2时，依旧需要考虑k和替换重复字符。当替换次数> (3-k)时，仅考虑替换次数p即可。否则，计算 (3-k) 。即为s = max( p , (3-k) )。
当k=3时，仅需要考虑替换掉重复字符s = p。 - n>20时
此时，至少要删除掉n-20个字符才能合格，还需要考虑k和替换连续重复的字段。这一部分较为复杂，先详细分析，再整理思路。
当k=1时，字符串仅包含一种字符，此时需要先删除n-20个字符，再进行替换20/3次替换。替换要进行6次。即此时至少要操作s = n-20+6次。
当k=2时或者当k=3时，考虑到删除一个连续（超过三个长度的）字符相当于一次替换操作，所以删除字符的时候可以减少替换的次数。
对于要进行删除字符的重复区间，主要分为三种情况，区间长度模3的余数为0，1，2。区间长度取模为0时，删除一个字符减少一次替换操作。区间长度取模为1时，删除两个字符减少一次替换操作。区间长度取模为2时，删除三个字符减少一次替换操作。对所有的重复字段进行一次上述操作以后，所有的重复字段都会变成区间长度取模为2的情况。
具体实现代码如下：
int strongPasswordChecker(char * password){
int chara = 0, charA = 0, charNum = 0;
int length = strlen(password);
int i = 0, j = 0, k = 0, s = 0, p = 0;
int delNum = 0;
int d[3][2] = {0};
while(i < length){
if(charNum != 1 && password[i] >= '0' && password[i] <= '9')
charNum = 1;
if(chara != 1 && password[i] >= 'a' && password[i] <= 'z')
chara = 1;
if(charA != 1 && password[i] >= 'A' && password[i] <= 'Z')
charA = 1;
if(password[i] == password[i+1] && i+2 <length){
j = i+2;
while(password[j] == password[i] && j < length){
j++;
}
d[(j-i)%3][0]++;
d[(j-i)%3][1] = d[(j-i)%3][1] + ((j-i)/3);
i = j - 1;
}
i++;
}
k = charNum+chara+charA;
p = d[0][1]+d[1][1]+d[2][1];
if(length <= 5){
s = (3-k)>(6-length)?(3-k):(6-length);
}else if(length>5 && length <21){
switch(k){
case 1:
case 3:
s = p;
break;
case 2:
s = p>(3-k)?p:(3-k);
break;
}
}else{
delNum = length - 20;
if(delNum > 0 && d[0][1] > 0){
if(d[0][0]<delNum){
delNum -= d[0][0];
d[2][1] += (d[0][1] - d[0][0]);
d[0][1] = 0;
}else{
d[0][1] -= delNum;
delNum = 0;
}
}
if(delNum > 0 && d[1][1] > 0){
if((d[1][0]*2)<delNum){
delNum -= (d[1][0]*2);
d[2][1] += (d[1][1] - d[1][0]);
d[1][1] = 0;
}else{
d[1][1] -= (delNum/2);
delNum = delNum % 2;
}
}
if(delNum > 0 && d[2][1] > 0){
d[2][1] -= (delNum/3);
delNum = delNum%3;
}
p = d[0][1]+d[1][1]+d[2][1];
s = p+(length-20);
s = ((p >= (3-k))?p:(3-k))+(length-20);
}
return s;
}
|