logo标签列表

不使用string.Split方法如何分割字符串？

c#string
6

我正在做一道家庭作业问题，要求不使用框架方法来分割字符串。

下面是我想出来的可行代码。

我想知道如何将运行时间提高到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);
}
你可以使用正则表达式吗？ - Desolator
不，我不允许。它应该是“C”式的！ - Nemo
是的，这是一个字符数组。 - Nemo
1
它应该有多像 C 语言？例如，foreach 是 C# 的语法，不是很像 C。 - Bertie
1
@Dialecticus 循环外的 if(buff.Length != 0) 是为了将未处理完的缓冲区写入结果。 - Nemo
显示剩余6条评论
5个回答
6
我有几个修改意见，可以让这个函数更加类似于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)：

不要为每个字符循环遍历分隔符，而应该提前循环遍历分隔符，并设置一个像这样的数组：

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

然后，您可以使用此数组在常数时间内测试字符串的每个字符。
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 编辑：我错误地提到了C＃的String.Split() API不能使用分隔符数组。
文档似乎与您对C#方法所需的分隔符不一致：http://msdn.microsoft.com/en-us/library/b873y76a.aspx。 - Bertie
这是不正确的。请参阅MSDN上的String.Split方法。 - Olivier Jacot-Descombes
你们说得没错。然而，我认为使用C# API的更高级用法在多个分隔符下不完全以O(n)的执行时间完成。我已经更新了我的答案来反映这一点。感谢指出。 - Localghost
1

如果您将分隔符字符放入 HashSet 中，则可以将其变为 O(n)。在 HashSet 中测试值的存在性是 O(1)。

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

...

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

然而，对于少量的分隔符，这并不会提高性能。

OP说解决方案必须是C'ish，因此请改用bool[]。另外，我真的怀疑HashSet在所有元素数量上都具有恒定的查找时间。这是如何实现的？ - David Grayson
请查看 Stack Overflow 上的问题 哈希表真的可以是 O(1) 吗？ - Olivier Jacot-Descombes
1

在O(n)的时间复杂度内执行String.Split是不可能的，因为需要遍历/搜索分隔符列表。

1
这样对吗？第一遍不应该是O(n)吗？然后第二遍也是O(n)，如果我没记错的话，O(2n)=O(n)，但是已经有一段时间了，所以我可能记错了。 - Michael
0

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

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;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接