Ray*_*ond 15 c# string algorithm
给定一个字符串,找出使该单词成为回文所需的最小字符数.例子:
ABBA : 0 (already a palindrome) ABB: 1 FAE: 2 FOO: 1
pax*_*blo 48
算法,因为这可能是家庭作业[道歉雷蒙德,这是一个面试问题,而不是作业,因为他的编辑/评论清楚.但是,算法和添加的伪代码仍然有效,我最后添加了一些C代码.
你需要在弦的末尾找到最长的回文.可以通过简单地从字符串的开头运行一个指针和从末尾运行一个指针来创建查看字符串是回文结构的算法,检查它们引用的字符是否相同,直到它们在中间相遇.就像是:
function isPalindrome(s):
i1 = 0
i2 = s.length() - 1
while i2 > i1:
if s.char_at(i1) not equal to s.char_at(i2):
return false
increment i1
decrement i2
return true
尝试使用完整的字符串.如果这不起作用,请将第一个字符保存在堆栈中,然后查看剩余的字符是否形成回文.如果这不起作用,请同时保存第二个字符,然后再从第三个字符开始检查.
最终你会得到一系列保存的字符和剩下的字符串,这是一个回文.
最好的情况是,如果原始字符串是回文,在这种情况下,堆栈将是空的.最坏的情况是剩下一个字符(一个字符的字符串自动为回文)和堆栈中的所有其他字符.
您需要添加到原始字符串末尾的字符数是堆栈中的字符数.
要实际制作回文,请逐个将字符从堆栈中弹出并将它们放在回文字符串的开头和结尾处.
例子:
String Palindrome Stack Notes
------ ---------- ----- -----
ABBA Y - no characters needed.
String Palindrome Stack Notes
------ ---------- ----- -----
ABB N -
BB Y A one character needed.
ABBA Y - start popping, finished.
String Palindrome Stack Notes
------ ---------- ----- -----
FAE N -
AE N F
E Y AF two characters needed.
AEA Y F start popping.
FAEAF Y - finished.
String Palindrome Stack Notes
------ ---------- ----- -----
FOO N -
OO Y F one character needed.
FOOF Y - start popping, finished.
String Palindrome Stack Notes
------ ---------- ----- -----
HAVANNA N -
AVANNA N H
VANNA N AH
ANNA Y VAH three characters needed.
VANNAV Y AH start popping.
AVANNAVA Y H
HAVANNAVAH Y - finished.
String Palindrome Stack Notes
------ ---------- -------- -----
deoxyribo N -
eoxyribo N d
oxyribo N ed
: : :
bo N iryxoed
o Y biryxoed eight chars needed.
bob Y iryxoed start popping.
ibobi Y ryxoed
: : :
oxyribobiryxo Y ed
eoxyribobiryxoe Y d
deoxyribobiryxoed Y - finished.
将此方法转换为"代码":
function evalString(s):
stack = ""
while not isPalindrome(s):
stack = s.char_at(0) + stack
s = s.substring(1)
print "Need " + s.length() + " character(s) to make palindrome."
while stack not equal to "":
s = stack.char_at(0) + s + stack.char_at(0)
stack = stack.substring(1)
print "Palindrome is " + s + "."
对于那些对伪代码不太感兴趣的人,这里有一个C语言中的测试程序.
#include <stdio.h>
#include <string.h>
static char *chkMem (char *chkStr) {
if (chkStr == NULL) {
fprintf (stderr, "Out of memory.\n");
exit (1);
}
return chkStr;
}
static char *makeStr (char *oldStr) {
char *newStr = chkMem (malloc (strlen (oldStr) + 1));
return strcpy (newStr, oldStr);
}
static char *stripFirst (char *oldStr) {
char *newStr = chkMem (malloc (strlen (oldStr)));
strcpy (newStr, &(oldStr[1]));
free (oldStr);
return newStr;
}
static char *addFront (char *oldStr, char addChr) {
char *newStr = chkMem (malloc (strlen (oldStr) + 2));
sprintf (newStr, "%c%s", addChr, oldStr);
free (oldStr);
return newStr;
}
static char *addBoth (char *oldStr, char addChr) {
char *newStr = chkMem (malloc (strlen (oldStr) + 3));
sprintf (newStr, "%c%s%c", addChr, oldStr, addChr);
free (oldStr);
return newStr;
}
static int isPalindrome (char *chkStr) {
int i1 = 0;
int i2 = strlen (chkStr) - 1;
while (i2 > i1)
if (chkStr[i1++] != chkStr[i2--])
return 0;
return 1;
}
static void evalString (char *chkStr) {
char * stack = makeStr ("");
char * word = makeStr (chkStr);
while (!isPalindrome (word)) {
printf ("%s: no, ", word);
stack = addFront (stack, *word);
word = stripFirst (word);
printf ("stack <- %s, word <- %s\n", stack, word);
}
printf ("%s: yes, need %d character(s)\n", word, strlen (stack));
printf ("----------------------------------------\n");
printf ("Adjusting to make palindrome:\n");
while (strlen (stack) > 0) {
printf (" %s, stack <- %s\n", word, stack);
word = addBoth (word, *stack);
stack = stripFirst (stack);
}
printf (" %s\n", word);
printf ("========================================\n");
free (word);
free (stack);
}
int main (int argc, char *argv[]) {
int i;
for (i = 1; i < argc; i++) evalString (argv[i]);
return 0;
}
运行此:
mkpalin abb abba fae foo deoxyribo
给出输出:
abb: no, stack <- a, word <- bb
bb: yes, need 1 character(s)
----------------------------------------
Adjusting to make palindrome:
bb, stack <- a
abba
========================================
abba: yes, need 0 character(s)
----------------------------------------
Adjusting to make palindrome:
abba
========================================
fae: no, stack <- f, word <- ae
ae: no, stack <- af, word <- e
e: yes, need 2 character(s)
----------------------------------------
Adjusting to make palindrome:
e, stack <- af
aea, stack <- f
faeaf
========================================
foo: no, stack <- f, word <- oo
oo: yes, need 1 character(s)
----------------------------------------
Adjusting to make palindrome:
oo, stack <- f
foof
========================================
deoxyribo: no, stack <- d, word <- eoxyribo
eoxyribo: no, stack <- ed, word <- oxyribo
oxyribo: no, stack <- oed, word <- xyribo
xyribo: no, stack <- xoed, word <- yribo
yribo: no, stack <- yxoed, word <- ribo
ribo: no, stack <- ryxoed, word <- ibo
ibo: no, stack <- iryxoed, word <- bo
bo: no, stack <- biryxoed, word <- o
o: yes, need 8 character(s)
----------------------------------------
Adjusting to make palindrome:
o, stack <- biryxoed
bob, stack <- iryxoed
ibobi, stack <- ryxoed
ribobir, stack <- yxoed
yribobiry, stack <- xoed
xyribobiryx, stack <- oed
oxyribobiryxo, stack <- ed
eoxyribobiryxoe, stack <- d
deoxyribobiryxoed
========================================