ABC324-C Error Correction

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5 ababc");
            WillReturn.Add("ababc");
            WillReturn.Add("babc");
            WillReturn.Add("abacbc");
            WillReturn.Add("abdbc");
            WillReturn.Add("abbac");
            //4
            //1 2 3 4
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1 aoki");
            WillReturn.Add("takahashi");
            //0
            //
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("9 atcoder");
            WillReturn.Add("atoder");
            WillReturn.Add("atcode");
            WillReturn.Add("athqcoder");
            WillReturn.Add("atcoder");
            WillReturn.Add("tacoder");
            WillReturn.Add("jttcoder");
            WillReturn.Add("atoder");
            WillReturn.Add("atceoder");
            WillReturn.Add("atcoer");
            //6
            //1 2 4 7 8 9
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string[] SplitArr = InputList[0].Split(' ');
        string TDash = SplitArr[1];

        var TList = new List<string>();
        for (int I = 1; I <= InputList.Count - 1; I++) {
            TList.Add(InputList[I]);
        }

        var AnswerList = new List<int>();

        for (int I = 0; I <= TList.Count - 1; I++) {
            string EachT = TList[I];
            if (Math.Abs(EachT.Length - TDash.Length) > 1) continue;

            if (EachT == TDash) {
                AnswerList.Add(I + 1);
                continue;
            }

            if (Check2(TDash, EachT)) {
                AnswerList.Add(I + 1);
                continue;
            }

            if (Check2(EachT, TDash)) {
                AnswerList.Add(I + 1);
                continue;
            }

            if (Check4(EachT, TDash)) {
                AnswerList.Add(I + 1);
                continue;
            }
        }

        AnswerList.Sort();
        Console.WriteLine(AnswerList.Count);
        Console.WriteLine(IntEnumJoin(" ", AnswerList));
    }

    // セパレータとInt型の列挙を引数として、結合したstringを返す
    static string IntEnumJoin(string pSeparater, IEnumerable<int> pEnum)
    {
        string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
        return string.Join(pSeparater, StrArr);
    }

    // 条件2の判定
    static bool Check2(string WillRemove, string RemovedStr)
    {
        if (RemovedStr.Length + 1 != WillRemove.Length) return false;

        var InsLinkedList1 = new LinkedList<char>();
        var InsLinkedList2 = new LinkedList<char>();

        foreach (char EachChar in WillRemove) InsLinkedList1.AddLast(EachChar);
        foreach (char EachChar in RemovedStr) InsLinkedList2.AddLast(EachChar);

        while (InsLinkedList1.Count > 0 && InsLinkedList2.Count > 0) {
            if (InsLinkedList1.First.Value == InsLinkedList2.First.Value) {
                InsLinkedList1.RemoveFirst();
                InsLinkedList2.RemoveFirst();
                continue;
            }

            if (InsLinkedList1.Last.Value == InsLinkedList2.Last.Value) {
                InsLinkedList1.RemoveLast();
                InsLinkedList2.RemoveLast();
                continue;
            }
            break;
        }

        int CntSum = InsLinkedList1.Count + InsLinkedList2.Count;
        return CntSum == 1;
    }

    // 条件4の判定
    static bool Check4(string pT, string pTDash)
    {
        if (pTDash.Length != pT.Length) {
            return false;
        }

        int UnMatchCnt = 0;

        for (int I = 0; I <= pTDash.Length - 1; I++) {
            if (pTDash[I] != pT[I]) {
                UnMatchCnt++;
            }
        }
        return UnMatchCnt == 1;
    }
}

解説

TとTDashでは、分かりにくいので
WillRemoveとRemovedStr
といった分かりやすい変数名に変更してます。

ABABC  に1文字追加して
ABACBC に変更できるかの判定を
線形で行う方法は、
LinkedListを2つ用意して、
先頭と末尾を見る方法が、バグりにくいです。