正在拆分没有字符串的字符串.分裂

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），然后在返回之前只调整一次大小。

2） 不要使用StringBuilder组合结果，而是制作一个长度为txt.Length的char[] buff和一个索引变量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;
}

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

Answer 2

我认为您的教授正在寻找一个只使用单个字符而不使用数组的API。不是字符数组。我的意思是，如果你的分隔字符串是"abcd"，你就不会在"a"、"b"、"c"、"d"的所有实例上进行拆分。只有找到整根绳子，你才会分开。

您当前的算法不是O（n），因为对于输入数组中的每个元素，您都要将其与定界数组的每个元素进行比较。这导致了O（n*m）的执行时间。

我认为不可能将其转换为O（n），因为输入上的每个元素都需要与分隔符数组的每个元素进行比较。我认为你的教授可能会就分隔符数组提出不同的问题。

public static String[] Split(String input, String delimiter)
{
    List<String> parts = new List<String>();
    StringBuilder buff = new StringBuilder();
    if (delimiter.Length > 1) //you are splitting on a string not a character
    {
       //perform string searching algorithm here
    }
    else if(delimiter.Length == 0)
    {
       throw new InvalidOperationException("Invalid delimiter.");
    }
    else //you are splitting on a character
    {
       char delimChar = delimiter[0];
       for (int i = 0; i < input.Length; i++)
       {
           if (input[i] == delimChar)
           {
               parts.Add(buff.ToString());
               buff.Clear();
           }
           else
           {
               buff.Append(input[i]);
           }
       }
    }
    return parts.ToArray();
}

C#的String.Split()确实接受了一个分隔符数组，但我不相信它能在O（n）时间内进行拆分。

如果您正在研究字符串搜索算法，这些算法可能会有所帮助。http://en.wikipedia.org/wiki/String_searching_algorithm

edit：我错误地提到了C#的String.Split() API没有采用分隔符数组的事实。

Answer 3

由于必须遍历/搜索分隔符列表，因此无法在O（n）中执行String.Split。

Answer 4

如果将分隔符放入HashSet，则可以将其设为O（n）。测试HashSet中是否存在值是O（1）。

var delimterSet = new HashSet<char>(delim);

if(delimterSet.Contains(txt[i]) { ... }

但是，对于少数分隔符，这不会提高性能。

Answer 5

也许你可以尝试在一次中完成所有工作

public static String[] Split(String txt, char[] delim)
{
    if (txt == null)
        return new String[0]; // or exception
    if (delim == null || delim.Length == 0)
        return new String[0]; // or exception
    char[] text = txt.ToCharArray();
    string[] result = new string[1]; // If there is no delimiter in the string, return the whole string
    int part = 0;
    int itemInArray = 1;
    for (int i = 0; i < text.Length; i++)
    {
        if (IsIn(delim, text[i]))
        {
            Array.Resize(ref result, ++itemInArray); // Is it consider as a framework method ???
            part++;
        }
        else
            result[part] += text[i];
    }
    return result;
}
public static Boolean IsIn(char[] delim, char c)
{
    for (int i = 0; i < delim.Length; i++)
        if (c == delim[i])
            return true;
    return false;
}