字符串中的额外字符 |力扣2707

Question

我在解决今天的每日 Leetcode 问题时陷入困境，我请求你们的帮助。这是任务：

给你一个 0 索引的字符串 s 和一个单词词典。您必须将 s 分成一个或多个不重叠的子字符串，以便每个子字符串都出现在字典中。 s 中可能存在一些任何子字符串中都不存在的额外字符。 如果您以最佳方式分解 s，则返回剩余的最少额外字符数。

这是我们得到的输入：

s = “rkmsilizktprllwoimafyuqmeqrujxdzgp”

字典= [“afy”，“lyso”，“ymdt”，“uqm”，“cfybt”，“lwoim”，“hdzeg”，“th”，“rkmsi”，“d”，“e”，“tp”，“ r”、“jx”、“tofxe”、“etjx”、“llqs”、“cpir”、“p”、“ncz”、“ofeyx”、“eqru”、“l”、“demij”、“tjky” ,“jgodm”,“y”,“ernt”,“jfns”,“akjtl”,“wt”,“tk”,“zg”,“lxoi”,“kt”]

我已经通过了 2020/2028 测试，但我只是不明白我的代码中的错误在哪里：

class Solution {
    public int minExtraChar(String s, String[] dictionary) {
        List<String> dictionary2 = new ArrayList<>(); 
        for (String str: dictionary){
            if (s.contains(str)){
                dictionary2.add(str);
            }
        }
        List<String> sorted = dictionary2.stream()
            .sorted(Comparator.comparingInt(String::length).reversed())
            .collect(Collectors.toList());
        for (String a: sorted){
            System.out.println(a);
        }
        for (String str: sorted){
            if (s.contains(str)){
                System.out.println("----------------------------");
                System.out.println(s);
                System.out.println(str);
                String ak = " ";
                ak = ak.repeat(str.length());
                s = s.replace(str,ak);
            }
        }
        s = s.replace(" ","");
        System.out.println(s);
        return s.length();
    }
}

输出应该是2，而我的输出是3。

我知道这不是解决这个问题的最传统方法，但是有没有办法改变这个代码以使其工作，或者我应该从头开始？

感谢您的所有帮助:)。

Answer 1

我也创建了一个类似的解决方案：

class Solution {
public int minExtraChar(String s, String[] dictionary) {
    StringBuilder b = new StringBuilder(s);

    Arrays.sort(dictionary, new Comparator<String>(){
        public int compare(String o1,String o2){
            int l1 = o1.length();
            int l2 = o2.length();
            return l2 - l1;
        }
    });

    System.out.println(Arrays.toString(dictionary));

    for(String k : dictionary){
        int idx = b.indexOf(k);
        while(idx!=-1){
            System.out.println(k);
            b.delete(idx,idx + k.length());
            idx = b.indexOf(k);
        }
    
    }

    System.out.println(b);
    return b.length();
}

}

但是正如 abra 所指出的，我的解决方案无法最佳地删除字符，我们必须考虑所有可能的字符串。