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

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.

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

标签： javastringalgorithm

Answer 1

首先，您提供的解释似乎是基于对问题的略微误解的表述。问题在于检查是否所有出现的字符都可以替换为字符串 s 中的不同字符，而不是数组中的字符串。

所以例如用s = "aabbcdbb", 和数组字符串"aabbbdbb"，你可以用 a替换其中的c字符来获得数组字符串。情况并非相反。这解释了两个输入样本的预期输出不一致（如评论中所述）。sb

您的实现通常是正确的，但在特殊情况下会失败。您解决它的方法基本上是生成一个“diff”数组，其中包含每个字符的出现差异。然后，您期望在差异中，您只有两个不同的事件相互否定。为了说明前面的示例，您映射 的字符s：

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

与当前数组元素类似：

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

不同之处在于：

b -> 1
c -> -1

当你有s = "aabb"一个 string时，这会失败"abbb"，其中 diff 是：

a -> -1
b -> 1

这里的问题是两个字符都a出现b在字符串中"abbb"。这应该会导致匹配检查失败。原因是：如果我们想要从"abbb"to "aabb"，我们需要将 a 替换为ban a。但是"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++;
        }
    }
}