问题描述
p401相关说明:本题为《算法竞赛入门经典(第2版)》例题 3-3
解法一:模拟
模拟读入,每次读一行字符串 s ,然后判断是否是回文串或镜像串:
- 回文串:对于每个 s[i] 都必须满足 s[i]==s[len-i-1], 这个验证起来比较简单;
- 镜像串:对于每个 s[i] 都必须满足 FindMirror(s[i])==s[len-i-1], 需要知道如何设计 FindMirror 函数
我们可以借助字符串常量 MIRR_ALPHAS 和 MIRR_NUMBER 来建立字符(字母和数字)到其镜像字符的映射 ,实现上用不同字符编码的相对偏移量当作对应索引值。同时这里在处理输出字符串时用到了一些技巧,由于回文串和镜像串都是简单的 0/1 关系,所以可以用二进制来映射所有的 NUM_CASE = 4 种情况。
容易忽视的地方:此题的输出需要在输入字符串后面接内容,因此在从标准流读入的时候记得关注换行符的处理。
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 |
#include <bits/stdc++.h> using namespace std; // For comparison: "ABCDEFGHIJKLMNOPQRSTUVWXYZ" char const* MIRR_ALPHAS = "A 3 HIL JM O 2TUVWXY5"; char const* MIRR_NUMBER = "1SE Z 8 "; // "123456789" const int NUM_CASE = 4; const array<string, NUM_CASE> SUFFIX = { " -- is not a palindrome.", " -- is a regular palindrome.", " -- is a mirrored string.", " -- is a mirrored palindrome."}; char FindMirror(const char& ch) { if (isalpha(ch)) return MIRR_ALPHAS[ch - 'A']; else // isdigit return MIRR_NUMBER[ch - '1']; } int main() { string s; while (getline(cin, s)) { int len = s.size(); bool is_palindrome = 1, is_mirrored = 1; for (int i = 0; (is_palindrome || is_mirrored) && i < (len + 1) / 2; ++i) { char mirr_char = FindMirror(s[i]); if (mirr_char != s[len - i - 1]) is_mirrored = 0; if (s[i] != s[len - i - 1]) is_palindrome = 0; } cout << s + SUFFIX[is_palindrome + is_mirrored * 2] << "\n\n"; } } |
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 |
MIRR_ALPHAS = "A 3 HIL JM O 2TUVWXY5" MIRR_NUMBER = "1SE Z 8 " SUFFIX = [" -- is not a palindrome.", " -- is a regular palindrome.", " -- is a mirrored string.", " -- is a mirrored palindrome."] def find_mirr_char(ch): return MIRR_ALPHAS[ord(ch) - ord("A")] if ch.isalpha() else MIRR_NUMBER[ord(ch) - ord("1")] while True: try: line = input() is_palindrome = 1 is_mirrored = 1 for i, _ in enumerate(line): mirr_char = find_mirr_char(line[i]) if mirr_char != line[len(line) - i - 1]: is_mirrored = 0 if line[i] != line[len(line) - i - 1]: is_palindrome = 0 print(line + SUFFIX[is_palindrome + is_mirrored * 2], end="\n\n") except EOFError: break |