从字符串中删除列表或数组的元素

Question

我有一个字符串列表或数组

String [] elements = {"cat", "dog", "fish"};

以及一个字符串

String str = "This is a caterpillar and that is a dogger.";

我想从字符串中删除所有在数组/列表中存在的元素，然后函数应该返回一个新的字符串。

str = "This is a erpillar and that is a ger." (cat and dog removed from the string)

我可以做这样的事情。

private String removeElementsFromString (String str, String [] elements) {
        if(Arrays.stream(elements).anyMatch(str::contains)){
            for(String item : elements){
                str = str.replace(item, "");
            }
        }
        return str;
    }

但是，将for循环改为其他形式的优雅方法是什么？

- AL̲̳I

---

我有一个字符串列表或数组。这是一个数组，不是一个列表。 - Andy Turner

你想针对像“docatg”（中间有猫的狗）这样的内容做什么？你想先移除猫，再移除狗吗？还是只想移除猫？ - Andy Turner

请注意这样的情况：elements = {"cat", "catcher",...}。如果先移除"cat"，那么短语就变成了"pass it to her"。 - Charlie G

你也可以有竞争性的重叠，比如 ["app","ply"]。对于短语 "apply"，我们可以去掉 "app" 留下 "ly"，或者去掉 "ply" 留下 "ap"。 - Charlie G

Answer 1

一句话解决方案

以下的一行代码即可完成任务：

str = str.replaceAll(Arrays.stream(elements).map(s -> "(?:" + s + ")").collect(Collectors.joining("|")), "");

演示:

import java.util.Arrays;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) {
        String[] elements = { "cat", "dog", "fish" };
        String str = "This is a caterpillar and that is a dogger.";
        
        str = str.replaceAll(Arrays.stream(elements).map(s -> "(?:" + s + ")").collect(Collectors.joining("|")), "");

        System.out.println(str);
    }
}

输出：

This is a erpillar and that is a ger.

在线演示

解释：

Arrays.stream(elements).map(s -> "(?:" + s + ")").collect(Collectors.joining("|")) 的结果是正则表达式 (?:cat)|(?:dog)|(?:fish)，其含义是匹配 cat 或 dog 或 fish。

下一步是将该正则表达式替换为 ""。

- Arvind Kumar Avinash

---

我的评论第二次被删除，没有任何解释。这个解决方案对于任何输入字符串都不起作用（例如 ":)"）。你能证明这不是真的吗？ - josejuan

Answer 2

使用StringBuilder的另一种解决方案：

因为它速度更快，消耗的内存更少。

我认为在这里使用StringBuilder而不是String更加适合：

import java.io.IOException;
import java.util.stream.Stream;

public class Bounder {

public static void main(String[] args) throws IOException {
    String[] elements = { "cat", "dog", "fish" };
    String str = "This is a catcatcatcatcatcatcaterpillar ancatcatcatcatd thcatcatcatat is a dogdogdogdogdogdogger.";
// Use StringBuilder here instead of String     
StringBuilder bf = new StringBuilder(str);
    str =null;

    System.out.println("Original String   =  " + bf.toString());
    Stream.of(elements).forEach(e -> {
        int index = bf.indexOf(e);
        while (index != -1) {
            index = bf.indexOf(e);
            if (index != -1) {
                bf.delete(index, index + e.length());
            }
        }
    });

    System.out.println("Result            =  " + bf.toString());
}
}

输出：

  Original String   =  This is a catcatcatcatcatcatcaterpillar ancatcatcatcatd thcatcatcatat is a dogdogdogdogdogdogger.

  Result            =  This is a erpillar and that is a ger.

- Oussama ZAGHDOUD

---

你的解决方案仍然具有O(n^2)的成本，如果你真的想要一个高效的解决方案，请使用成本为O(n)的Aho-Corasick算法。 - josejuan

Answer 3

Arrays.stream(elements).reduce(str, (r, w) -> r.replace(w, ""))

带有预期输出。

如果您想将输入字符串缩小到不再可能，最好迭代直到没有更改为止。

String n = str, o = null;
do {
    n = stream(elements).reduce(o = n, (r, w) -> r.replace(w, ""));
} while(!n.equals(o));

System.out.println(n);

然后，使用输入字符串。

This is a caterpillar and that is a docatg.

你将获得

This is a erpillar and that is a .

如果您真的需要一种快速算法，请使用成本为O(n)的Aho-Corasick

    StringBuilder sb = new StringBuilder();
    int begining = -1;
    for (Emit e : Trie.builder().addKeywords(elements).build().parseText(str)) {
        sb.append(str, begining + 1, e.getStart());
        begining = e.getEnd();
    }
    sb.append(str, begining + 1, str.length());

    System.out.println(sb.toString());

Aside 解决方案性能比较（与 Oussama ZAGHDOUD 的解决方案相比）：

Equals = true       // check all output are equals
Time1 = 18,548822   // Oussama ZAGHDOUD's solution O(n^2)
Time2 = 0,134459    // Aho-Corasick O(n) without precompute Trie
Time3 = 0,065056    // Aho-Corasick O(n) precomputed Trie

全面的工作代码

static String alg1(String[] elements, String str) {
    StringBuilder bf = new StringBuilder(str);
    str =null;
    Stream.of(elements).forEach(e -> {
        int index = bf.indexOf(e);
        while (index != -1) {
            index = bf.indexOf(e);
            if (index != -1) {
                bf.delete(index, index + e.length());
            }
        }
    });
    return bf.toString();
}

static String alg2(String[] elements, String str) {
    StringBuilder sb = new StringBuilder();
    int begining = -1;
    for (Emit e : Trie.builder().addKeywords(elements).build().parseText(str)) {
        sb.append(str, begining + 1, e.getStart());
        begining = e.getEnd();
    }
    sb.append(str, begining + 1, str.length());

    return sb.toString();
}

static String alg3(Trie trie, String str) {
    StringBuilder sb = new StringBuilder();
    int begining = -1;
    for (Emit e : trie.parseText(str)) {
        sb.append(str, begining + 1, e.getStart());
        begining = e.getEnd();
    }
    sb.append(str, begining + 1, str.length());

    return sb.toString();
}

public static void main(String... args) throws JsonProcessingException {

    final ThreadLocalRandom rnd = ThreadLocalRandom.current();

    // test, use random numbers as words
    String[] elements = range(0, 1_000).mapToObj(i -> "w" + rnd.nextInt()).toArray(String[]::new);

    // intercalate random elements word with other random word
    String str = range(0, 100_000)
            .mapToObj(i -> "z" + rnd.nextInt() + " " + elements[rnd.nextInt(elements.length)])
            .collect(joining(", "));

    Trie trie = Trie.builder().addKeywords(elements).build();

    long t0 = System.nanoTime();
    String s1 = alg1(elements, str);
    long t1 = System.nanoTime();
    String s2 = alg2(elements, str);
    long t2 = System.nanoTime();
    String s3 = alg3(trie, str);
    long t3 = System.nanoTime();

    System.out.printf("Equals = %s%nTime1 = %f%nTime2 = %f%nTime3 = %f%n",
            s1.equals(s2) && s2.equals(s3), (t1 - t0) * 1e-9, (t2 - t1) * 1e-9, (t3 - t2) * 1e-9);
}

- josejuan

---

@初学者 你认为我的评论是负面的，因为它们指出了那些解决方案中的缺陷。这些缺陷是在那些解决方案中还是在我的评论中？想想你是在寻找真相还是只是为了安于现状而误导自己。（那么其他人为什么删除了他们之前的评论呢？） - josejuan

Answer 4

我会简单地使用：

private String removeElementsFromString(String str, String[] elements) {
    for (String item : elements) {
        str = str.replace(item, "");
    }
    return str;
}

我没有看到第一个条件的任何优势：

if(Arrays.stream(elements).anyMatch(str::contains)) {

- Youcef LAIDANI

Answer 5

最简洁的方法是使用replaceAll，它接受一个正则表达式作为第一个参数：

String newStr = str.replaceAll(String.join("|", elements), "");

这仅适用于elements中的内容没有特殊的正则表达式字符。如果其中任何一个有（或有可能有），您必须对它们进行引用：

String pattern = Arrays.stream(elements).map(Pattern::quote).collect(Collectors.joining("|"));

---

请注意，这将在单个传递中运行。因此，如果您有像这样的字符串：

docatg

这种方法会导致dog，而使用input.replace("cat", "").replace("dog", "")的方法会同时移除dog。

- Andy Turner

---

不，单词不是正则表达式。 - josejuan

@josejuan 我不明白你的意思。一些单词是有效的正则表达式。所有被引用的模式字符串都是有效的正则表达式。 - Andy Turner

Answer 6

你可以这样做。只需使用简单的循环即可。

for (String word : elements) {
            str = str.replace(word,"");
}

- WJS