洛谷:P1098:字符串的展开


洛谷:P1098:字符串的展开

题目

P1098:字符串的展开

分析

这道题考验的是读懂题意,然后分层级模拟要求的过程。

是否能展开?

题目中有明确的展开条件,一般而言:如果-两侧字符都是小写字母或都是数字,那么是可以进行展开处理的。其中的特例是,如果两侧的字母或数字正好相邻,那么删除-号即可。例如:

  • a-d可以展开。进入后续处理。
  • a-b不用展开。而应该跳过-(不将这个字符加入到结果中),而进行后续处理。
  • z-c/0-a不用展开。

我们用一个函数来辅助判定。

bool expandable(char left, char right)
{
    if ((islower(left) && isalpha(right)) || (isdigit(left) && isdigit(right)))
    {
        if (right > left)
        {
            return true;
        }
    }

    return false;
}

注意,这里用嵌套if比较好,因为必须保证-两侧的字符都是一个类型,才能安全地进行大小的判定。不然,小写字母永远大于数字的!

用什么字符填充

接着我们要判定用什么字符填充。这个是由p1确定的。将其翻译为:

char getFillChar(char c, int p1)
{
    char fill = c;
    if (p1 == 2 && islower(c))
    {
        fill = toupper(c);
    }
    else if (p1 == 3)
    {
        fill = '*';
    }

    return fill;
}

构成填充字符串

这个由p2确定。将其翻译为:

string getFillString(char fill, int p2)
{
    string tmp;
    for (int i = 0; i < p2; i++)
    {
        tmp += fill;
    }
    return tmp;
}

要不要反转

完成填充字符串的拼接后,最后要看p3,确定是否要将拼好的字符串翻转:

for (char c = left + 1; c < right; c++)
{
    char fill = getFillChar(c, p1);
    tmp += getFillString(fill, p2);
}
if (p3 == 2)
{
    reverse(tmp.begin(), tmp.end());
}

result += tmp;

注意:反转一定要在完成整个拼接字符串之后再做。

特殊情形处理

我们有两个特殊情况需要处理。

  1. 如果当前字符是-,但不能扩展,那么-需要保留。
  2. 如果是一般字符,那么直接添加到结果中即可。

另一个特殊情形,是可以“扩展”,但因为-左右两个字符相邻,所以要去掉-号。这个也很简单:

if (i > 0 && i < s.length() - 1 && s[i] == '-')
{
    char left = s[i - 1], right = s[i + 1];
    if (expandable(left, right))
    {
        string tmp;
        if (left == right - 1)
        {
            continue;
        }
    // ...

}

另外,我们在遍历字符串的时候,也要注意判定-的位置——因为我们要读取-前后([i-1]/[i+1])的字符。

答案

Solution

思考

请特别注意边界与鲁棒性

  • 索引边界:判断 s[i]=='-' 时确保 i>0 && i+1 < s.size()
  • 非法字符:题目通常只给字母/数字和 -,如需健壮性可为其他字符分支保留原样;
  • 连续多个 -:逐个按规则处理,不要跨位合并。

Previous Next