s******c
发帖数: 99 | 1 https://www.interviewstreet.com/challenges/dashboard/#problem/4edb8abd7cacd
简单说来，就是计算String 和所有suffix 的similarity并加和
比如 ababaa
所有suffix是 "ababaa", "babaa", "abaa", "baa", "aa" and "a"
他们与ababaa 的similarity 是 6,0,3,0,1,1 所以结果就是 6+3+0+0+1+1=11
另一个例子 aa
suffix是"aa","a"
similarity 就是 2, 1，结果是2+1=3
我的算法是先定义一个similarity function,计算任意两String的similarity值。在处
理问题的时候，生成所有的suffix，string有多长，就有多少个suffix，然后计算每个
suffix和原来String的similarity，最后相加。
运行的结果是只过了4/10个testcase。之后的报错是time limited exceeded. 做过的
人知道是什么原因吗？下面把代码贴上。 | s******c
发帖数: 99 | 2 import java.io.*;
public class Solution {
public static void main(String args[] ) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.
in));
String line = br.readLine();
int N = Integer.parseInt(line);
String []strs=new String[N];
for (int i = 0; i < N; i++) {
strs[i]=br.readLine();
}
for(int i=0;i
{
char start=strs[i].charAt(0);
int sumtotal=0;
StringBuffer ss=new StringBuffer();
int iLen=strs[i].length();
for(int j=iLen-1;j>=0;j--)
{
char c=strs[i].charAt(j);
ss.insert(0,c);
if(c!=start)
continue;
int sim=getSim(ss, strs[i]);
sumtotal+=sim;
}
System.out.println(sumtotal);
}
}
public static int getSim(StringBuffer s1, String s2)
{
int len=s1.length();
if(s2.length()
len=s2.length();
int similar=0;
for(int i=0;i
{
if(s1.charAt(i)!=s2.charAt(i))
return similar;
else
similar++;
}
return similar;
}
} |
|
