emu in blogjava

是不是用動態(tài)規(guī)劃來做？
任何一個符合題意的字串，要么有一個中心字符，要么兩個兩個相鄰字符相同
因此，
1，把每個字符，或者每兩個相鄰字符相同的pair記錄到一個集合
2，對1的集合中所有元素，向左右個擴展一個字符，如果這兩個字符相同則記錄，不同則計數(shù)，并扔出集合。
循環(huán)直到全部元素被扔出。
  回復  更多評論
  

我的python解法：


def MaximalPalindromeSubstrings(s):
xxflag=-1
count=0
for i in range(0,len(s)):
sta=i
sed=flag=len(s)-1

while sed>sta and flag>xxflag:

if s[sta]==s[sed]:
sed-=1
sta+=1
continue
else:
sta=i
sed=flag
sed-=1
flag-=1
if flag>xxflag:
count+=1
xxflag=flag

if sta==sed:
print s[(flag-2*(flag-sta)):(flag+1)]
if sta>sed:
print s[((flag-2*(flag-sta))-1):(flag+1)]
if xxflag==len(s)-1:
break
return count
xx='abacabbacaacdbdcacxcbbbbcabababacccbazhhaahh'
ret=MaximalPalindromeSubstrings(xx)

print 'count:',ret
  回復  更多評論
  

public static int countMaximalPalindromeSubstrings(String[] str)
{

String target = "";
int length = str.length;
for (int i=0; i< length;i++)
{
target += str[i];
}
length = target.length();

int head = 0;
int tail = length -1;

char c1,c2;
int head_tmp = head;
int tail_tmp = tail;
boolean recover = false;
int count =0;
int h_length =0;
int last_h_length =0;
boolean finished = false;

for (;!finished;head++)
{

h_length = 0;
c1 = target.charAt(head);

head_tmp = head;

int head1 = head_tmp;
int tail1 = tail;

for (tail_tmp = tail;head_tmp<tail_tmp;)
{
if (recover)
{
h_length=0;
head_tmp = head1;
tail1--;
tail_tmp = tail1 ;
}

c1 = target.charAt(head_tmp);
c2 = target.charAt(tail_tmp);
if (c1 == c2)
{
recover = false;
head_tmp ++;
tail_tmp --;
h_length +=2;
continue;
}
else
{
recover = true;

}
}
if (tail1 == length-1)
{
finished = true;
}
if (head_tmp==tail_tmp)
{
h_length += 1;
}
else if (Math.abs(head_tmp-tail_tmp) == 2)
h_length -= 1;

if (last_h_length < head + h_length)
{
count ++;
last_h_length = h_length+head;
}
}


return count;

}  回復  更多評論