如果你想
检查句子B中从句子A中删除的单词，Java中最好的方法是什么？例如：
A句：我想删除这句简单句子中不必要的单词。
B句：我想删除这句话的字。
输出：我想删除这个（简单）句子上的（不必要的）单词。
其中括号内的单词是从句子 A 中删除的单词。
假设顺序无关紧要：使用共享资源集合。
- 使用
String.split()将两个句子拆分为单词数组。 - 使用共享资源集合
CollectionUtils.addAll将每个数组添加到空Set中。 - 使用共享资源集合的
CollectionUtils.subtract方法获得A-B。
假设顺序和位置很重要，这看起来就像是最长公共子序列问题的变体，这是一个动态规划解决方案。
维基百科有一个关于这个主题的很棒的页面，我真的太多了，无法在这里概述
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
其他人都在使用非常重量级的算法来解决实际上非常简单的问题。它可以使用最长的公共子序列来解决，但它是一个非常受约束的版本。这不是一个完整的差异;它仅包括删除。不需要动态编程或类似的东西。下面是一个 20 行的实现：
private static String deletedWords(String s1, String s2) {
StringBuilder sb = new StringBuilder();
String[] words1 = s1.split("\s+");
String[] words2 = s2.split("\s+");
int i1, i2;
i1 = i2 = 0;
while (i1 < words1.length) {
if (words1[i1].equals(words2[i2])) {
sb.append(words1[i1]);
i2++;
} else {
sb.append("(" + words1[i1] + ")");
}
if (i1 < words1.length - 1) {
sb.append(" ");
}
i1++;
}
return sb.toString();
}
当输入是问题中的输入时，输出完全匹配。
当然，我知道对于某些输入有多种解决方案。例如：
a b a
a
可能是a (b) (a)的，也可能是(a) (b) a的，也许对于这个问题的某些版本，这些解决方案之一比另一个更有可能是"实际"解决方案，对于那些你需要一些递归或动态编程方法......但是，我们不要让它比以色列佐藤最初要求的要复杂得多！
String a = "I want to delete unnecessary words on this simple sentence.";
String b = "I want to delete words on this sentence.";
String[] aWords = a.split(" ");
String[] bWords = b.split(" ");
List<String> missingWords = new ArrayList<String> ();
int x = 0;
for(int i = 0 ; i < aWords.length; i++) {
String aWord = aWords[i];
if(x < bWords.length) {
String bWord = bWords[x];
if(aWord.equals(bWord)) {
x++;
} else {
missingWords.add(aWord);
}
} else {
missingWords.add(aWord);
}
}
这很好用....对于更新的字符串也
更新了用方括号括起来的字符串。
import java.util.*;
class Sample{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
String str1 = sc.nextLine();
String str2 = sc.nextLine();
List<String> flist = Arrays.asList(str1.split("\s+"));
List<String> slist = Arrays.asList(str2.split("\s+"));
List<String> completedString = new ArrayList<String>();
String result="";
String updatedString = "";
String deletedString = "";
int i=0;
int startIndex=0;
int endIndex=0;
for(String word: slist){
if(flist.contains(word)){
endIndex = flist.indexOf(word);
if(!completedString.contains(word)){
if(deletedString.isEmpty()){
for(int j=startIndex;j<endIndex;j++){
deletedString+= flist.get(j)+" ";
}
}
}
startIndex=endIndex+1;
if(!deletedString.isEmpty()){
result += "("+deletedString.substring(0,deletedString.length()-1)+") ";
deletedString="";
}
if(!updatedString.isEmpty()){
result += "["+updatedString.substring(0,updatedString.length()-1)+"] ";
updatedString="";
}
result += word+" ";
completedString.add(word);
if(i==slist.size()-1){
endIndex = flist.size();
for(int j=startIndex;j<endIndex;j++){
deletedString+= flist.get(j)+" ";
}
startIndex = endIndex+1;
}
}
else{
if(i == 0){
boolean boundaryCheck = false;
for(int j=i+1;j<slist.size();j++){
if(flist.contains(slist.get(j))){
endIndex=flist.indexOf(slist.get(j));
boundaryCheck=true;
break;
}
}
if(!boundaryCheck){
endIndex = flist.size();
}
if(!completedString.contains(word)){
for(int j=startIndex;j<endIndex;j++){
deletedString+= flist.get(j)+" ";
}
}
startIndex = endIndex+1;
}else if(i == slist.size()-1){
endIndex = flist.size();
if(!completedString.contains(word)){
for(int j=startIndex;j<endIndex;j++){
deletedString+= flist.get(j)+" ";
}
}
startIndex = endIndex+1;
}
updatedString += word+" ";
completedString.add(word);
}
i++;
}
if(!deletedString.isEmpty()){
result += "("+deletedString.substring(0,deletedString.length()-1)+") ";
}
if(!updatedString.isEmpty()){
result += "["+updatedString.substring(0,updatedString.length()-1)+"] ";
}
System.out.println(result);
}
}
这基本上是一个不同的，看看这个：
- 差异
和根算法：
- 最长的常见子序列问题
下面是一个示例 Java 实现：
- http://introcs.cs.princeton.edu/java/96optimization/Diff.java.html
比较线条。您唯一需要做的就是按单词而不是按行拆分，或者将两个句子的每个单词放在单独的行中。
例如，如果在 Linux 上，您实际上可以在编写任何代码之前使用程序本身diff查看后一个选项的结果，请尝试以下操作：
$ echo "I want to delete unnecessary words on this simple sentence."|tr " " "n" > 1
$ echo "I want to delete words on this sentence."|tr " " "n" > 2
$ diff -uN 1 2
--- 1 2012-10-01 19:40:51.998853057 -0400
+++ 2 2012-10-01 19:40:51.998853057 -0400
@@ -2,9 +2,7 @@
want
to
delete
-unnecessary
words
on
this
-simple
sentence.
前面有-的行是不同的（或者，如果将这些行添加到句子 B 中，而不在句子 A 中，它会显示+）。尝试一下，看看这是否适合您的问题。
希望这有帮助。