发信人: babbage (tm), 信区: Programming
标 题: Re: [转载] CS Interview question
发信站: Unknown Space - 未名空间 (Wed Dec 8 00:44:07 2004), 转信
Let's say that the input string is S, S..S[N] are the chars.
The question is to find all pairs (i,j) such that:
1) i<j, and
2) S[i+k] == S[j-k] for all k=0 to j-i. (actually to (j-i)/2 is sufficient.)
-- this is the same as saying S[i..j] is a palindrome.
Let us use boolean array A[i][j] to store if S[i..j] is a palin, then
1) A[i][i]=true, and
2) A[i][i+1]=true iff S[i]=S[i+1], and
3) A[i][j]=true iff A[i+1][j-1] is true && S[i]==S[j]
So we can use 1) and 2) to initialize all, A[i][i] and A[i][i+1]
and use 3) as the dynamic programming step when j>=i+2:
/* 1 */ for k=2 to N-1 // k is (j-i)
/* 2 */ for i=1 to N-k
/* 3 */ A[i][i+k] = A[i+1][i+k-1] && (S[i]==S[j])
Now we know if S[i..j] is a palindrome! It takes O(N^2) time.
This is probably optimal. Because there are strings that contains O(N^2)
palindromes, for example, S= "ABABABABAB...." (N repetitions of AB,
where every odd-length substring is a palindrome.
【 在 lhict (至少还有我) 的大作中提到: 】
: Create a function findPalin() that takes a string of characters as argument
: and returns the number of palindromes (a string in which the sequence of cha
: racters is the same forwards and backwards) in that string. There is no spec
: ial character. This function should be as fast as possible.
: "aa" returns 1
: "aabb" returns 2
: "222" returns 3
: "baaab3" returns 4
Ipso facto delecto!
※ 来源:．Unknown Space - 未名空间 mitbbs.com．[FROM: 24.218.]