替换一个字符及其所有出现后，计算匹配字符串的数量

Question

我有一个字符串数组arr和另一个输入字符串s。

现在我的任务是从s中选择一个字符，并用另一个字符替换s中所有出现的该字母。然后重新排列字符（可选）。现在计算有多少个匹配数组元素。

我已经用Java编写了代码，但我遵循的方法不正确。

例子: s = aabbcdbb

arr = {"aabbcdbbb", "aabbcdb", "aabbxdbb", "aabbbdbb", "aacccdcc", "ddbbcdbb", "eebbcdbb"}

输出：

5

说明:

length of s = 8
sorting s = aabbbbcd

arr[0] = has 9 characters i.e more than s length so ignored
arr[1] = has 7 characters i.e less than s length so ignored
arr[2] = sorting : aabbbbdx. replace x with c and rearranging it makes this as aabbbbcd
arr[3] = sorting : aabbbbbd. replace 1 occurrence of b with c and rearranging it makes this as aabbbbcd
arr[4] = sorting : aacccccd. replace 4 occurrences of c with b and rearranging it makes this as aabbbbcd
arr[5] = sorting : bbbbcddd. replace 2 occurrences of d with a and rearranging it makes this as aabbbbcd
arr[6] = sorting : bbbbcdee. replace e with a and rearranging it makes this as aabbbbcd

so arr[2], arr[3], arr[4], arr[5], arr[6] matches the given requirement so output is 5.

我尝试了这个程序，但对于某些输入它会失败:

static int process(String s, String[] arr) {
    int matches = 0;
    Map<Character, Integer> m = new HashMap<>();
    
    // sort s
    char[] c = s.toCharArray();
    Arrays.sort(c);
    s = new String(c);
    c = s.toCharArray();
    
    // get each char of s and count its occurrences
    for(char k : c) {
        m.put(k, m.getOrDefault(k, 0)+1);
    }
    
    for(String s1 : arr) {
        // get array element
        char[] c1 = s1.toCharArray();
        // check if array element length matches with input string length
        if(c1.length == c.length) {
            // count each occurrence of char into array of alphabets
            int[] chars = new int[26];
            for(char k1: c1) {
                chars[k1-'a']++;
            }
            
            // decrement count by checking with map
            for(char k : m.keySet()) {
                chars[k-'a'] -= m.get(k);
            }
            
            boolean f1 = false;
            boolean valid = true;
            int mismatch = 0;
            int notzeros = 0;
            // get each element from array of chars
            for(int i=0; i<26; i++) {
                int ch = chars[i];
                // value not zero
                if(ch != 0) {
                    // count number of non zeros
                    notzeros++;
                    // f1 is true, means its second occurrence of non zero element
                    if(f1) {
                        if(ch > 0) {
                            // check if values do not match
                            if(mismatch*-1 != ch) {
                                valid = false;
                                break;
                            }
                        } else {
                            // check if values do not match
                            if(mismatch != ch*-1) {
                                valid = false;
                                break;
                            }
                        }
                    }
                    // get the mismatch count and set the value of flag to true
                    f1 = true;
                    mismatch = ch;
                }
                // if non zero elements more than 2 then we can ignore this array element
                if(notzeros > 2) {
                    valid = false;
                    break;
                }
            }
            //  check for possible solution.
            if(valid && f1) {
                matches++;
            }
        }
    }
    return matches;
}

这个程序可以处理给定的测试用例。

但如果我发送下面的输入，它会失败。

example: s = abba
arr = {'aadd" ,"abbb"};

expected output: 1

explanation:
sorted s = aabb
arr[0] = aadd, replace d with b then we get aabb
arr[1] = abbb, we cannot replace all occurrences of a single character to get s as output, so ignored.

So the output is 1.

But my program is printing 2 which is not correct.

我的解决这个任务的方法不正确，正确的方法是什么？

- learner

---

这两个解释相互矛盾。在第一个解释中，您仅替换了某些字符的出现次数，这是可以的，但在第二个解释中则不行。如果像上面解释的那样（所有出现次数），那么第一个示例的答案应该是1。 - maraca

@maraca，是的，我错过了那个问题。这是在面试中被问到的，期望的输出与我的示例输入相同，对于两种情况都是如此。我对如何获得该输出的理解是不正确的。 - learner

@learner你还在寻找答案吗？ - Abhinav Mathur

注意，对于任何一个“示例”，都不会按照“从 s 中选择一个字符并替换该字母中的所有出现次数”的解释来操作。相反，对于arr中的每个字符串，它们尝试选择一个字符进行替换，并替换其中某些出现次数，并争论结果是否与s匹配。 - greybeard

嘿，学习者！这些答案有没有对你有用？ - Tomer Shetah

Answer 1

首先，你提供的解释似乎基于一个略微误解的问题陈述。问题是检查是否可以用不同的字符替换字符串 s 中的所有出现的字符，而不是数组中的字符串。

例如，对于 s = "aabbcdbb" 和数组字符串 "aabbbdbb"，您可以将 s 中的 c 字符替换为 b 以获得数组字符串。反之不成立。这解释了两个输入样例的预期输出存在矛盾的原因（如评论中所提出的）。

你的实现通常是正确的，但在一个特殊情况下失败了。你解决问题的方式基本上是生成一个“差异”数组，其中包含每个字符出现次数的差异。然后，你希望在差异中只有两个不同的出现次数相互抵消。为了说明前面的示例，你映射了 s 的字符:

a -> 2
b -> 4
c -> 1
d -> 1

与当前数组元素类似：

a -> 2
b -> 5
d -> 1

区别将会是：

b -> 1
c -> -1

当你有一个字符串s = "aabb"和另一个字符串"abbb"时，以下方法会失败，因为它们之间的差异是：

a -> -1
b -> 1

这里的问题在于字符串“abbb”中出现了字符a和b。这应该导致匹配检查失败。原因是：如果要从“abbb”变成“aabb”，我们需要用a替换一个b，但是“abbb”已经有了一个a字符，如果反过来将a替换为b，那么它就不会存在。

代码可以修改以处理此情况（使用diffInS1的部分）：

for(String s1 : arr) {
    // get array element
    char[] c1 = s1.toCharArray();
    // check if array element length matches with input string length
    if(c1.length == c.length) {
        // count each occurrence of char into array of alphabets
        int[] chars = new int[26];
        int[] diff = new int[26];
        for(char k1: c1) {
            chars[k1-'a']++;
            diff[k1-'a']++;
        }
        
        // decrement count by checking with map
        for(char k : m.keySet()) {
            diff[k-'a'] = chars[k-'a'] - m.get(k);
        }
        
        boolean valid = true;
        int mismatch = 0;
        int notzeros = 0;
        int diffInS1 = 0;
        // get each element from array of chars
        for(int i=0; i<26; i++) {
            int ch = diff[i];
            // value not zero
            if(ch != 0) {
                // count number of non zeros
                notzeros++;
                // second occurrence of non zero element
                if(notzeros > 1) {
                    // check if values do not match
                    if(mismatch*-1 != ch) {
                        valid = false;
                        break;
                    }
                }
                if(chars[i] > 0) {
                    diffInS1++;
                }
                // get the mismatch count
                mismatch = ch;
            }
            // if non zero elements more than 2 then we can ignore this array element
            if(notzeros > 2 || diffInS1 == 2) {
                valid = false;
                break;
            }
        }
        //  check for possible solution.
        if(valid && notzeros > 0) {
            matches++;
        }
    }
}

- M A

---

不看代码，我希望得到一个简洁的描述，如何从“字符直方图”得出真值“替换匹配”。 - greybeard

Answer 2

我将提供一种相似的方法。让我们分析何时两个字符串是“替换一个字符及其所有出现后匹配字符串”。假设我们有2个char计数的映射表。现在我们需要计算它们之间的差异。当左侧的两个映射表都具有一个条目，并且计数器相等时，两个字符串是匹配的。

让我们举个例子。 aabbbbcd 将创建映射表：

a -> 2
b -> 4
c -> 1
d -> 1

aabbxdbb将创建：

a -> 2
b -> 4
x -> 1
d -> 1

差异将是：

第一个映射将保留：

c -> 1

第二个地图:

x -> 1

因此，这两个匹配。让我们看看如何编写它。

首先，这是获取此地图的方法：

private static Map<Character, Integer> getMap(String s) {
    Map<Character, Integer> result = new HashMap<>();
    for (char c : s.toCharArray()) {
        if (result.containsKey(c)) {
            result.put(c, result.get(c) + 1);
        } else {
            result.put(c, 1);
        }
    }
    return result;
}

现在我们可以定义一个方法来创建谓词：

private static Predicate<String> getPredicate(String s) {
    Map<Character, Integer> sMap = getMap(s);
    Predicate<String> p = s1 -> {
        Map<Character, Integer> s1Map = getMap(s1);
        Map<Character, Integer> sMapCopy = getMap(s);

        for (Map.Entry<Character, Integer> kvp : sMap.entrySet()) {
            if (s1Map.containsKey(kvp.getKey())) {
                if (s1Map.get(kvp.getKey()) < kvp.getValue()) {
                    sMapCopy.put(kvp.getKey(), kvp.getValue() - s1Map.get(kvp.getKey()));
                    s1Map.remove(kvp.getKey());
                } else if (kvp.getValue() < s1Map.get(kvp.getKey())) {
                    s1Map.put(kvp.getKey(), s1Map.get(kvp.getKey()) - kvp.getValue());
                    sMapCopy.remove(kvp.getKey());
                } else {
                    sMapCopy.remove(kvp.getKey());
                    s1Map.remove(kvp.getKey());
                }
            }
        }

        boolean result = sMapCopy.size() == 1 && s1Map.size() == 1;
        if (result) {
            for (Map.Entry<Character, Integer> kvp : sMapCopy.entrySet()) {
                for (Map.Entry<Character, Integer> kvp1 : s1Map.entrySet()) {
                    System.out.println(s + " and " + s1 + " can be replaced. Replace " + kvp.getValue() + " instances of " + kvp.getKey() + " with " + kvp1.getValue() + " instances of " + kvp1.getKey());
                }
            }
        } else {
            System.out.println(s + " and " + s1 + " cannot be replaced.");
        }
        return result;
    };

    return p;
}

然后我们运行以下命令：

String[] strings = {"aabbcdbbb", "aabbcdb", "aabbxdbb", "aabbbdbb", "aacccdcc", "ddbbcdbb", "eebbcdbb"};
long result = Arrays.stream(strings).filter(getPredicate("aabbcdbb")).count();
System.out.println("Replacables count: " + result);

然后我们得到输出：

aabbcdbb and aabbcdbbb cannot be replaced.
aabbcdbb and aabbcdb cannot be replaced.
aabbcdbb and aabbxdbb can be replaced. Replace 1 instances of c with 1 instances of x
aabbcdbb and aabbbdbb can be replaced. Replace 1 instances of c with 1 instances of b
aabbcdbb and aacccdcc can be replaced. Replace 4 instances of b with 4 instances of c
aabbcdbb and ddbbcdbb can be replaced. Replace 2 instances of a with 2 instances of d
aabbcdbb and eebbcdbb can be replaced. Replace 2 instances of a with 2 instances of e
Replacables count: 5

- Tomer Shetah