使用分而治之的方法背后的推理

Question

我正在尝试在 LeetCode 上解决 this question:

A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase. For example, "abABB" is nice because 'A' and 'a' appear, and 'B' and 'b' appear. However, "abA" is not because 'b' appears, but 'B' does not.
Given a string s, return the longest substring of s that is nice. If there are multiple, return the substring of the earliest occurrence. If there are none, return an empty string.
For s = "YazaAay", the expected output is: "aAa"

其中一个 top voted solutions 使用分而治之的方法：

class Solution {
    public String longestNiceSubstring(String s) {
        if (s.length() < 2) return "";
        char[] arr = s.toCharArray();
        Set<Character> set = new HashSet<>();
        for (char c: arr) set.add(c);
        for (int i = 0; i < arr.length; i++) {
            char c = arr[i];
            if (set.contains(Character.toUpperCase(c)) && set.contains(Character.toLowerCase(c))) continue;
            String sub1 = longestNiceSubstring(s.substring(0, i));
            String sub2 = longestNiceSubstring(s.substring(i+1));
            return sub1.length() >= sub2.length() ? sub1 : sub2;
        }
        return s; 
    }
}

我了解它的工作原理，但不了解使用分而治之方法背后的直觉。换句话说，如果我已经忘记了所有的问题days/weeks之后再重新审视这个问题，我将无法意识到这是一个分而治之的问题。

是什么 'thing' 使它可以通过分而治之的方法解决？

Answer 1

分而治之，用维基百科的话说，当一个问题可以分解为“2 个或更多子问题”时是最合适的。这里的解法检查输入字符串是否满足条件，然后在每个字符处一分为二，递归检查字符串是否满足条件，直到无解。一般来说，分治法的应用很容易让人感觉到什么时候可以对称地细分问题，例如在计算一组点的 delaunay 三角剖分的 DeWall 算法中（http://vcg.isti.cnr.it/publications/papers/dewall.pdf - 很酷的东西).

在这个例子中，子字符串问题的不同之处在于它检查 all (edit:) ~~possible~~ viable subdivisions by incrementing the line细分。为了向可能感到困惑的任何人澄清，这是必要的，因为字符串不能从中间拆分，否则您可能会拆分像“aAaA”这样的子字符串，最后只返回一半。这种满足“两个或更多问题”中的更多条件，但我同意在这种情况下它不直观。

希望这对您有所帮助，我最近在实现参考算法时不得不学习很多这方面的知识。有更多经验的人可能会有更好的答案。

Answer 2

算法可以这样用简单的英语描述：

如果整个字符串都很好，我们就完成了。

否则，一定有一个字符只存在一种情况。这样一个字符自然地将字符串分成了两个子串。 分别征服他们中的每一个，并比较结果。

编辑：顺便说一句，我不认为这是 D&C 问题的一个很好的例子。关键是，一旦我们遇到第一个“坏”字符，它左边的子串就很好。没有必要深入其中。只需记录它的长度并继续前进。这是一个简单的循环。

使用分而治之的方法背后的推理

Reasoning behind using a divide and conquer approach

java

algorithm

divide-and-conquer