刚做的一个公司的在线编程题,简单来说,就是比对两个数组,查看是否能够匹配成同一个单词。
代码是不够精简,不过哪里出问题了,导致分数那么低...
题目
Java 代码
public boolean solution(String S, String T) {
// write your code in Java SE 8
int SLength = 0;
int TLength = 0;
String[] SParts = S.split("[^\\d]+");
String[] TParts = T.split("[^\\d]+");
for(int i = 0; i < SParts.length; i++) {
if(!SParts[i].equals("")){
SLength += Integer.parseInt(SParts[i]);
}
}
for(int i = 0; i < TParts.length; i++) {
if(!TParts[i].equals("")){
TLength += Integer.parseInt(TParts[i]);
}
}
for(int i = 0; i < S.length(); i++) {
if(!Character.isDigit(S.charAt(i))){
SLength += 1;
}
}
for(int i = 0; i < T.length(); i++) {
if(!Character.isDigit(T.charAt(i))){
TLength += 1;
}
}
if(TLength != SLength) {
return false;
}
char[] sArray = S.toCharArray();
char[] tArray = T.toCharArray();
char[] sArrayFiltered = new char[SLength];
char[] tArrayFiltered = new char[TLength];
int sIndex = 0;
int tIndex = 0;
for(int i = 0; i < sArray.length; i++) {
if(Character.isDigit(sArray[i])) {
sIndex += Character.getNumericValue(sArray[i]);
} else {
sArrayFiltered[sIndex] = sArray[i];
sIndex++;
}
}
for(int i = 0; i < tArray.length; i++) {
if(Character.isDigit(tArray[i])) {
tIndex += Character.getNumericValue(tArray[i]);
} else {
tArrayFiltered[tIndex] = tArray[i];
tIndex++;
}
}
for (int i = 0; i < SLength; i++) {
if (sArrayFiltered[i]=='\0' || tArrayFiltered[i]=='\0') continue;
if (sArrayFiltered[i] != tArrayFiltered[i]) return false;
return true;
}
return true;
}
结果
1
starvedcat 2016-09-17 12:42:50 +08:00
楼主你是 correctness 只有 12%啊
|
2
shliujing OP @starvedcat run 的时候, 4 个用例都通过了,我才 submit 的。。。略坑。而且写算法时时间有点急,来不及优化了
|
3
guokeke 2016-09-17 12:54:20 +08:00 via Android
算法有疏忽,那不是分。
|
4
shliujing OP 找到问题了。
![]( http://i4.piimg.com/567571/3b208ecd7bc527b1.png) 多了这行,导致如果两个字母匹配成功后就跳出;实际情况应该继续往下匹配,因为后面有可能还有不匹配的! 哎,还是怪自己平时算法写的不多。 |
5
GentleSadness 2016-09-17 17:41:05 +08:00 via Android
kmp 算法,如果想写正则表达式, dfa
|
6
wodesuck 2016-09-17 18:44:06 +08:00
@GentleSadness 跟 kmp 没关系,并不是匹配子串,只是个简单模拟题
|
7
GentleSadness 2016-09-17 22:53:23 +08:00
@wodesuck ? kmp 算法又称“看毛片”算法,是一个效率非常高的字符串匹配算法。他把前缀和后缀对比,减少了匹配时间
|
8
wodesuck 2016-09-19 22:40:45 +08:00
@GentleSadness 我知道 kmp 是什么……只是这题不是 kmp
|