拆分字符串没有string.Split

Question

我正在做一个家庭工作问题,不使用框架方法拆分字符串.

以下是我提出的工作代码.

我想知道如何改善O(n)的运行时间？

此外,欢迎任何改进建议.

public static string[] split(string txt, char[] delim)
{
    char[] text = txt.ToCharArray();
    string[] result = new string[0];
    int count = 0;
    int i = 0;
    StringBuilder buff = new StringBuilder(); 
    while(i < text.Length)
    {
        bool found = false;
        foreach(char del in delim)
        {
            if(del == txt[i])
            {
                found = true;
                break;
            }
        }
        if(found)
        {
            count++;
            Array.Resize(ref result, count);
            result[count - 1] = buff.ToString();
            buff = new StringBuilder();                 
        }
        else
        {
            buff.Append(txt[i]);
        }

        i++;
    }

    if(buff.Length != 0)
    {
        count++;
        Array.Resize(ref result, count);
        result[count - 1] = buff.ToString();
    }

    return(result);
}

Answer 1

我有一些更改会同时使这个函数更像C,并将运行时间减少到O(n):

1)result你应该多次动态地调整数组的大小,而不是动态地调整你的数组大小,你应该用足够的点来创建它来保存最大数量的字符串(你知道这个数字小于txt.Length),然后在返回它之前在最后调整它一次.

取而代之的组装与一个StringBuilder你的结果2),做一个char[] buff长度txt.Length和索引变量j做buff[j++] = txt[i].

我认为你的功能应该是O(N).从技术上讲,它将是O(N*M),其中M是分隔符的数量.

编辑1:

这是一个改变,它将使O(N)+ O(M)而不是O(N*M):

您应该循环遍历ADVANCE中的分隔符并设置如下所示的数组,而不是循环遍历字符串中每个字符的分隔符:

bool[] isDelimiter = new bool[128];  // increase size if you are allowing non-ascii
foreach(char delim in isDelimiter)
{
    isDelimiter[(int)char] = true;
}

然后你可以使用这个数组在恒定时间内测试字符串的每个字符.