Problem 401 Palindromes，判斷字的類型

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

(表一)

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

(表二)

此題輸入一字串，要判斷它是如表二所說的哪一種字串。
第一種：不是回文字串，意思就是說它是下述三種都不符合的情況下，
        才為這種字串。
第二種：為一正規回文字串，回文字就是對稱的字串，也就是不管你從
        左邊或右邊讀，都是一樣的，例如字串 ABCBA 、 ABCCBA，皆
        是回文字。
第三種：為一鏡照字，依照表一鏡照對照表可以觀察鏡照字，而鏡照字
        串就是從左邊讀會與鏡照後從右邊讀的字串一樣。
第四種：為一鏡照回文字，綜合第二、第三種條件的字串。

一開始可以寫一鏡照轉換函式，傳入字元即可傳出鏡照字元，如果找不到，回傳空白字串，C 語言程式碼如下：

char mirroredChar(char ch)
{
    if (ch == 'A') return 'A';
    if (ch == 'E') return '3';
    if (ch == '3') return 'E';
    if (ch == 'H') return 'H';
    if (ch == 'I') return 'I';
    if (ch == 'J') return 'L';
    if (ch == 'L') return 'J';
    if (ch == 'M') return 'M';
    if (ch == 'O') return 'O';
    if (ch == 'S') return '2';
    if (ch == '2') return 'S';
    if (ch == 'T') return 'T';
    if (ch == 'U') return 'U';
    if (ch == 'V') return 'V';
    if (ch == 'W') return 'W';
    if (ch == 'X') return 'X';
    if (ch == 'Y') return 'Y';
    if (ch == 'Z') return '5';
    if (ch == '5') return 'Z';
    if (ch == '1') return '1';
    if (ch == '8') return '8';
    if (ch == '0') return '0';
    return ' ';
}

接著，定義兩整數，用來判斷是否為違規鏡照字或回文字的規定，int isPalindrome = 1, isMirrored = 1;，讀入字串後，判斷字串中間點( 如果從字串兩側進行也可以 )，定義左側字串索引 left，右側字串索引 right，依序往左右進行判斷。如果此次 left 索引字元鏡照後不等於 right 索引字元，則違規鏡照字的規定，定義 isMirrored = 0;；若此次的 left 索引字元不等於 right 索引字元，則違規回文字的規定，定義 isPalindrome = 0;。如此判斷下去，直到超出索引位置之前。以上觀念寫成 C 語言程式碼如下：

int left, right;  
len = strlen(str);

/* 判斷中間點 */
if (len % 2) left = len / 2, right = left;
else left = len / 2 - 1, right = left + 1;

char leftCh, rightCh;
for ( ;left >= 0 && right < len; left --, right ++)
{
    leftCh = str[left];
    rightCh = str[right];
    if ( mirroredChar(leftCh) != rightCh ) isMirrored = 0;
    if ( leftCh != rightCh ) isPalindrome = 0;
}
printf("%s -- ", str);
if (isMirrored && isPalindrome) printf("is a mirrored palindrome.");
else if (isMirrored) printf("is a mirrored string.");
else if (isPalindrome) printf("is a regular palindrome.");
else printf("is not a palindrome.");
printf("\n\n");

By David.K

p401題目連結
回ACM題庫目錄
回首頁