我的算法在确定一个字符串需要替换多少个字母以替换另一个字符串时存在什么缺陷

本文关键字:替换 字符串 多少 另一个 缺陷 在什么 存在 算法 我的 一个 | 更新日期: 2023-09-27 18:01:05

我已经盯着这个看了半个小时,不知道哪里出了问题!在一些测试用例中,我得到了明显不正确的count答案。我已经测试了程序的每个子程序,它按预期工作。那么WTF呢?

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{    
    static void Main(String[] args)
    {
        int T = Int32.Parse(Console.ReadLine());
        for(int t = 0; t < T; ++t)
        {
            string str = Console.ReadLine();
            if(str.Length % 2 == 1) // str couldn't be split into halves
            {
                Console.WriteLine(-1);
                continue;
            }
            // determine how many replacements s1 needs to be an anagram of s2
            int n = str.Length / 2;
            string s1 = str.Substring(0, n);
            string s2 = str.Substring(n, n);
            int[,] counter = new int[26,2]; // counter[i,j] will be the # of occurences of the i-th letter
                                            // of the alphabet in string sj
            int ascii_a = (int)'a'; 
            for(int i = 0; i < n; ++i)
            {
                counter[(int)s1[i] - ascii_a, 0] += 1;
                counter[(int)s2[i] - ascii_a, 1] += 1;
            }
            // sum difference of occurences in each letter, and divide sum by 2
            int count = 0;
            for(int i = 0; i < n; ++i)
            {
                count += Math.Abs(counter[i, 0] - counter[i, 1]);
            }
            count /= 2; 
            Console.WriteLine(count);
        }
    }
}

测试输入:

aaabbb
ab
abc
mnop
xyyx
xaxbbbxx

我的输出:

3
0
-1
0
0
1

预期输出:

3
1
-1
2
0
1

我的算法在确定一个字符串需要替换多少个字母以替换另一个字符串时存在什么缺陷

s2被分配为:

string s2 = str.Substring(n, n);

我猜你想用

string s2 = str.Substring(n, str.Length);

我认为这应该可以解决您遇到的问题,但您当前的输出对于第一个输入来说非常准确