算法

C++算法题-奇奇怪怪的字符串修饰(Simple Pig Latin)

题目

codewar 链接

Move the first letter of each word to the end of it, then add “ay” to the end of the word. Leave punctuation marks untouched.

给定一条字符串，将每个单词的第一个字母移到最后面，在单词末尾添加 “ay”。标点符号不变。

例子：

1
2

pigIt('Pig latin is cool'); // igPay atinlay siay oolcay
pigIt('Hello world !');     // elloHay orldway !

代码：

1
2
3
4

std::string pig_it(std::string str)
{
    // Code here
}

个人题解

我的办法算不上很好，有点像糊出来的。在遍历原字符串的过程中用了多个嵌套判断在寻求能够通过的代码逻辑，很是勉强。若觉得实在过于离谱，还挺跳往他人题解。

我需要判断是否为单词。如果为单词，那我将这个单词抽出来按题目要求修饰不就好了吗？
所以，可以遍历 str 的过程中用 isalpha() 这个古早的 c 函数进行判断。(std::string 单个元素的类型为 char。) 先创建两个 string 一个用于保存结果返回、一个用于保存单词用于修饰。

1
2

    std::string res;
    std::string temp;

接着循环 str。

1

    for (int i = 0; i < str.size(); ++i){}

对每个元素进行判断，如果是字母就保存进 temp。

1
2
3

        if (isalpha(str[i])) {
            temp += str[i];
        }

如果不是字母呢，就要开始进行修饰并添加到 res 中去，要注意这个元素也是要原封不动地添加进去的。 在这里，修饰相关的内容是要复用多次的，将它封装成 std::string modify() 会好些:

1
2
3
4
5
6

std::string modify(std::string raw) {
    raw += (raw[0]);
    raw.erase(0, 1);
    raw += "ay";
    return raw;
}

好像像这样简单处理下就可以了?

1
2
3

        if (!isalpha(str[i])){
            res += modify(temp) + str[i];
        }

其实不然，真正的灾难才刚刚开始……
首先如果末尾是字母，那是不会修饰的，甚至都不会到 res 中去，因而需要在 if (isalpha(str[i]) 循环中添加判断字母是否为结尾，如果是就修饰并添加到 res。
因为判断是否为结尾也需要复用多次，所以也封装成函数:

1
2
3
4
5
6

bool isEnd(std::string str, int pos) {
    if (pos == str.size() - 1)
        return true;
    else
        return false;
}

因而只需要一行就行:

1

            if (isEnd(str, i)) res += modify(temp);

具体的 !isalpha 有点复杂，如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

        if (!isalpha(str[i])) {
            if (isalpha(str[i - 1])) {
                temp = modify(temp);
                if (isEnd(str, i)) {
                    res += temp;
                    break;
                }
            }
            res += temp + str[i];
            temp.clear();
        }
    }

有点解释不清(💩)
整体代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <bits/stdc++.h>

bool isEnd(std::string str, int pos) {
    if (pos == str.size() - 1)
        return true;
    else
        return false;
}

std::string modify(std::string raw) {
    raw += (raw[0]);
    raw.erase(0, 1);
    raw += "ay";
    return raw;
}

std::string pig_it(std::string str) {
    std::string res;
    std::string temp;

    for (int i = 0; i < str.size(); i++) {
        if (isalpha(str[i])) {
            temp += str[i];
            if (isEnd(str, i)) res += modify(temp);
        }
        if (!isalpha(str[i])) {
            if (isalpha(str[i - 1])) {
                temp = modify(temp);
                if (isEnd(str, i)) {
                    res += temp;
                    break;
                }
            }
            res += temp + str[i];
            temp.clear();
        }
    }

    return res;
}

他人题解

我的方法其实就是原初💩山，大可不用观摩。

正则表达式法

1
2
3
4
5
6
7

#include <string>
#include <regex>
using namespace std;
string pig_it(string Z) {
    regex reg(("(\\w)(\\w*)(\\W|$)"));
    return regex_replace(Z, reg, "$2$1ay$3");
}

因为在 C++ 中 \ 是转义字符，所以要使用 \\ 来转换成 \。，因而这个 reg 正则表达式实际是:(\w)(\w*)(\W|$)

  • (\w)匹配一个字母和下划线，Pig Latin 也不会出现下划线，因而没事。
    这里是要处理单词第一个字母。在之后会对应到 $1 去。
  • (\w*) 匹配后面剩下的字母，单词剩下部分。对应到 $2。
    * 匹配前面模式零次或多次。也就是匹配之后的单词出现零次或多次。
  • (\W|$) 匹配非单词符号或字符串结尾位置。对应到 $3。

这样比如我们的字符串是 Hello, World:
就会匹配到 Hello, 和 World。

往后 regex_replace(Z, reg, "$2$1ay$3") 进行正则替换，显然之前的正则表达式会匹配每一个字母并分成三部分并忽略空白符和标点符号。
而接下来要对这三部分进行处理，也就是按题目所需：
先出现后面的字母，接着是开头的字母，并添上 ay。之后加上后面的符号。
上面的例子在这里会被转变成:
elloH, 和 orldW，然后连接在一起。

regex_replace() 的用法:

1

    std::regex_replace(const Ch_type *s, const basic_regex<Ch_type, Rx_traits> &e, const basic_string<Ch_type, St, Sa> &fmt)
参数 作用 实例
const Ch_type *s 指定要处理的文本 Z
basic_regex<Ch_type, Rx_traits> &e 表明匹配规则 reg (这里的参数应该是 regex对象，在创建的时候就可以说明处理规则。)
const basic_string<Ch_type, St, Rx_traits> &e 重新排列和构建文本的模板 “$2$1ay$3”
萌ICP备20241614号