2015去哪儿网校园招聘笔试题：寻找字符串的差异

哪儿的一道笔试题。


给定两个字符串a，b；找出两个字符串中不一样的字符串。如存在于a而不存在于b，则将该字符输出，同时、加一个“-”标记；若存在于b而不存在于a，则输出该字符，同时以“+”标记。若是同时存在于a、b中，则不输出。假设字符串是由字母组成。


如：


a="abc",b="aabcbc",则输出为"+a,+b,+c"；

a="abcde",b="bcdef",则输出为“-a,+f”；

思路：

我们可以使用上一篇讲到的寻找两个字符串的公共子串的方法。即先找到两个字符串的最长公共子串，做相应的处理，然后找次长的公共子串，做相同的处理；直到两个字符串没有公共子串。

package com.liuhao.acm.exam;

public class StringDiff {

public String diff(String a, String b){
String result = "";
LongestComSub lcs = new LongestComSub();

while(true){

//获取两个字符串的最长公共子串
String maxSub = lcs.getLongestComSub(a, b);

//若没有公共子串，则跳出while
if(maxSub.length() == 0){
break;
}

//将公共子串全部替换掉
a = a.replaceAll(maxSub, "0");
b = b.replaceAll(maxSub, "1");

}

//将a中剩下的输出
for(int i=0; i<a.length();i++){
if(a.charAt(i) != '0'){
result += ("-" + a.charAt(i) + ",");
}
}

for(int i=0; i<b.length();i++){
if(b.charAt(i) != '1'){
result += ("+" + b.charAt(i) + ",");
}
}

result = result.substring(0, result.length()-1);

return result;
}

public static void main(String[] args) {
String a = "abcbc";
String b = "aabcaa";
System.out.println(new StringDiff().diff(a, b));
}

}