hdu 1318 Palindromes

Palindromes

Time Limit:3000MS     Memory Limit:0KB     64bit 
                                                                                        IO Format:%lld & %llu

Description

A regular palindrome is a string of numbers or letters that is the same forward as backward. For example, the string "ABCDEDCBA" is a palindrome because it is the same when the string is read from left to right as when the string is read from right to left.

A mirrored string is a string for which when each of the elements of the string is changed to its reverse (if it has a reverse) and the string is read backwards the result is the same as the original string. For example, the string "3AIAE" is a mirrored string because "A" and "I"are their own reverses, and "3" and "E" are each others' reverses.

A mirrored palindrome is a string that meets the criteria of a regular palindrome and the criteria of a mirrored string. The string"ATOYOTA" is a mirrored palindrome because if the string is read backwards, the string is the same as the original and because if each of the characters is replaced by its reverse and the result is read backwards, the result is the same as the original string.

Of course,"A","T", "O", and "Y" are all their own reverses.

A list of all valid characters and their reverses is as follows.

Character Reverse Character Reverse Character Reverse
A A M M Y Y
B   N   Z 5
C   O O 1 1
D   P   2 S
E 3 Q   3 E
F   R   4  
G   S 2 5 Z
H H T T 6  
I I U U 7  
J L V V 8 8
K   W W 9  
L J X X    

Note that O (zero) and 0 (the letter) are considered the same character and therefore ONLY the letter "0" is a valid character.

Input

Input consists of strings (one per line) each of which will consist of one to twenty valid characters. There will be no invalid characters in any of the strings. Your program should read to the end of file.

Output

For each input string, you should print the string starting in column 1 immediately followed by exactly one of the following strings.

STRING CRITERIA
" -- is not a palindrome." if the string is not a palindrome and is not a mirrored string
" -- is a regular palindrome." if the string is a palindrome and is not a mirrored string
" -- is a mirrored string." if the string is not a palindrome and is a mirrored string
" -- is a mirrored palindrome." if the string is a palindrome and is a mirrored string

Note that the output line is to include the -'s and spacing exactly as shown in the table above and demonstrated in the Sample Output below.

In addition, after each output line, you must print an empty line.

Sample Input

NOTAPALINDROME
ISAPALINILAPASI
2A3MEAS
ATOYOTA

Sample Output

NOTAPALINDROME -- is not a palindrome.

ISAPALINILAPASI -- is a regular palindrome.

2A3MEAS -- is a mirrored string.

ATOYOTA -- is a mirrored palindrome.

Hint

use the C++'s class of string will be convenient, but not a must

【思路】

回文 --即从左至右与从右至左一样,例如:abccab 、aaa、abcba.......

镜像字符串--字符串里的字符都属于镜像字符,且从左至右与字符镜像呈回文。例如:AEH3A(A-A E-3).....

建立两个方法判断回文与判断镜像字符串(见代码)。

回文部分读者自看。

判断镜像字符串,传人字符串,先判断字符串中是否有字符不属于镜像字符,如果有直接返回false,没有在进行下一步扫描

本代码中建立了对应的x1字符数组,存放对应的镜像。x数组存放镜像字符,x1对应x存放其镜像。

从头开始扫描,i从头,j从尾扫描。在x字符数组中扫描找到其c[i]字符在x数组对应的下标k(x1[k]为其镜像),然后判断c[j]与x[k]是否相等(即对应的尾部字符是否是其字符对应的镜像字符),若相等镜像匹配成功,依次扫描,扫描到最后返回true。

【小坑,其中所有的‘0’(零)用‘O’(哦)来代替,看清楚】

 

AC代码:

import java.util.Scanner;

public class Main {
public static boolean pali(String s) {
char[] c = s.toCharArray();
int i, j;
for (i = 0, j = c.length - 1; i < j; i++, j--) {
if (c[i] != c[j]) {
return false;
}
}
return true;
} public static boolean mirr(String s) {
char[] c = s.toCharArray();
int i, j;
char[] x = new char[] { 'A', 'E', 'H', 'I', 'J', 'L', 'M', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '1', '2',
'3', '5', '8', 'O' };
for (i = 0; i < c.length; i++) {
for (j = 0; j < x.length; j++) {
if (c[i] == x[j]) {
break;
}
}
if (j == x.length) {
return false;
}
}
int k = 0;
char[] x1 = new char[] { 'A', '3', 'H', 'I', 'L', 'J', 'M', '2', 'T', 'U', 'V', 'W', 'X', 'Y', '5', '1', 'S',
'E', 'Z', '8', 'O' };
for (i = 0, j = c.length - 1; i < j; i++, j--) {
for (k = 0; k < x.length; k++) {
if (c[i] == x[k]) {
if (c[j] != x1[k]) {
return false;
}
}
}
}
return true;
} public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String s = sc.nextLine();
char[] a = s.toCharArray();
for (int i = 0; i < a.length; i++) {
if (a[i] == '0')
a[i] = 'O';
}
String str = new String(a);
if (pali(str) && mirr(str)) {
System.out.println(str + " -- is a mirrored palindrome.");
} else if (pali(str)) {
System.out.println(str + " -- is a regular palindrome.");
} else if (mirr(str)) {
System.out.println(str + " -- is a mirrored string.");
} else
System.out.println(str + " -- is not a palindrome.");
System.out.println();
}
}
}

  

上一篇:STL-- vector中resize()和reserve()区别


下一篇:dp --- Codeforces 245H :Queries for Number of Palindromes