algorithm - 删除字符串中的连续重复项以生成最小的字符串

Question

给定一个字符串和匹配 >= 3 个字符的约束，如何确保结果字符串尽可能小？

用 gassa 的明确性编辑:

例如'AAAABBBAC'

如果我先删除 B，AAAA[BBB]AC --> AAAAAC，然后我可以从结果字符串中删除所有 A，并留下:

[AAAAA]C --> C

'C'

如果我只删除第一个可用的(A 的序列)，我会得到:

[AAAA]BBBAC --> [BBB]AC --> AC

'AC'

Answer 1

一棵树肯定会给你最短的字符串。

树的解决方案:

1. 定义一个State (节点)对于每个当前 string Input及其所有可移动子字符串' int[] Indexes .
2. 创建树:对于每个 int index创建另一个 State并将其添加到父状态 State[] Children .
3. A State没有可能的可移动子字符串没有 child Children = null .
4. 获取所有后代 State[]你的根 State .按最短的顺序排列 string Input .这就是你的答案。

测试用例:

string result = FindShortest("AAAABBBAC");      // AC
string result2 = FindShortest("AABBAAAC");      // AABBC
string result3 = FindShortest("BAABCCCBBA");    // B

代码:

注意:当然，欢迎大家在性能和/或修复任何错误方面增强以下代码。

class Program
{
    static void Main(string[] args)
    {
        string result = FindShortest("AAAABBBAC");      // AC
        string result2 = FindShortest("AABBAAAC");      // AABBC
        string result3 = FindShortest("BAABCCCBBA");    // B
    }

    // finds the FIRST shortest string for a given input
    private static string FindShortest(string input)
    {
        // all possible removable strings' indexes
        // for this given input
        int[] indexes = RemovableIndexes(input);

        // each input string and its possible removables are a state
        var state = new State { Input = input, Indexes = indexes };

        // create the tree
        GetChildren(state);

        // get the FIRST shortest
        // i.e. there would be more than one answer sometimes
        // this could be easily changed to get all possible results
        var result = 
            Descendants(state)
            .Where(d => d.Children == null || d.Children.Length == 0)
            .OrderBy(d => d.Input.Length)
            .FirstOrDefault().Input;


        return result;
    }

    // simple get all descendants of a node/state in a tree
    private static IEnumerable<State> Descendants(State root)
    {
        var states = new Stack<State>(new[] { root });
        while (states.Any())
        {
            State node = states.Pop();
            yield return node;
            if (node.Children != null)
                foreach (var n in node.Children) states.Push(n);
        }
    }

    // creates the tree
    private static void GetChildren(State state)
    {
        // for each an index there is a child
        state.Children = state.Indexes.Select(
                i =>
                {
                    var input = RemoveAllAt(state.Input, i);
                    return input.Length < state.Input.Length && input.Length > 0
                    ? new State
                    {
                        Input = input,
                        Indexes = RemovableIndexes(input)
                    }
                    : null;
                }).ToArray();

        foreach (var c in state.Children)
            GetChildren(c);
    }

    // find all possible removable strings' indexes
    private static int[] RemovableIndexes(string input)
    {
        var indexes = new List<int>();

        char d = input[0];
        int count = 1;
        for (int i = 1; i < input.Length; i++)
        {
            if (d == input[i])
                count++;
            else
            {
                if (count >= 3)
                    indexes.Add(i - count);

                // reset
                d = input[i];
                count = 1;
            }
        }
        if (count >= 3)
            indexes.Add(input.Length - count);


        return indexes.ToArray();
    }

    // remove all duplicate chars starting from an index
    private static string RemoveAllAt(string input, int startIndex)
    {
        string part1, part2;

        int endIndex = startIndex + 1;
        int i = endIndex;
        for (; i < input.Length; i++)
            if (input[i] != input[startIndex])
            {
                endIndex = i;
                break;
            }

        if (i == input.Length && input[i - 1] == input[startIndex])
            endIndex = input.Length;

        part1 = startIndex > 0 ? input.Substring(0, startIndex) : string.Empty;
        part2 = endIndex <= (input.Length - 1) ? input.Substring(endIndex) : string.Empty;

        return part1 + part2;
    }

    // our node, which is 
    // an input string & 
    // all possible removable strings' indexes
    // & its children
    public class State
    {
        public string Input;
        public int[] Indexes;

        public State[] Children;
    }
}