如果要检查从句子 B 中的句子 A 中删除的单词,Java 中的最佳方法是什么。例如:
句子A:我想删除这个简单句子上不必要的单词。
句子 B:我想删除这句话上的单词。
输出:我想删除这个(简单)句子中的(不必要的)单词。
其中括号内的单词是从句子 A 中删除的单词。
假设顺序无关紧要:使用公共集合。
String.split()
将两个句子拆分为单词数组。CollectionUtils.addAll
将每个数组添加到一个空的Set
.CollectionUtils.subtract
方法获取 AB。假设顺序和位置很重要,这看起来像是最长公共子序列问题的一种变体,一种动态规划解决方案。
wikipedia 有一个关于这个主题的很棒的页面,我在这里要概述的实在太多了
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
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);
}
}
其他人都在使用重量级算法来解决实际上非常简单的问题。它可以使用最长公共子序列来解决,但它是一个非常受限的版本。这不是一个完整的差异;它只包括删除。不需要动态编程或类似的东西。这是一个 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
对于这个问题的某些版本,其中一个解决方案比另一个更可能是“实际”解决方案,对于那些你需要一些递归或动态编程方法的人......但我们不要这样做比Israel Sato最初要求的要复杂得多!
这很好用....对于更新的字符串,也
更新了用方括号括起来的字符串。
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 实现:
比较线条。您唯一需要做的就是按单词而不是按行拆分,或者将两个句子的每个单词放在单独的行中。
如果例如在 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 中没有)。试试看是否适合您的问题。
希望这可以帮助。