分割字符串没有string.Split [英] Splitting string without string.Split

问题描述

我做了家庭作业问题，不使用框架的方法来分割字符串。

以下是我想出了工作代码。

我想知道我怎么能提高运行时间为O（N）？

同样在改进建议都欢迎。

 公共静态字符串[]分裂（字符串TXT，CHAR [] DELIM）
 {
的char [] =文字txt.ToCharArray（）; 
的String []结果=新的字符串[0]; 
诠释计数= 0; 
 INT I = 0; 
 StringBuilder的BUFF =新的StringBuilder（）; 
，而（I< text.Length）
 {
布尔发现= FALSE; 
的foreach（字符德尔DELIM）
 {
如果（德尔== TXT [I]）
 {
发现= TRUE; 
中断; 
} 
} 
如果（找到）
 {
计数++; 
 Array.Resize（REF结果，计数）; 
结果[数 -  1] = buff.ToString（）; 
 BUFF =新的StringBuilder（）; 
} 
，否则
 {
 buff.Append（TXT [I]）; 
} 
 
 I ++; 
} 
 
如果（buff.Length！= 0）
 {
计数++; 
 Array.Resize（REF结果，计数）; 
结果[数 -  1] = buff.ToString（）; 
} 
 
返回（结果）; 
} 
  

解决方案

我有一些变化了将同时使该功能更多的C一样，并减少运行时间为O（n）：

1），而不是动态调整你的结果数组很多次，你应该有足够的点创建它来保存字符串的最大数量（你知道数小于 txt.Length ）和然后在返回之前快结束的调整只是一次。

而不是用一个StringBuilder组装你的结果2），使的char [] BUFF 长度 txt.Length 和索引变量Ĵ做的buff [J ++] = TXT [I] 。

我想你的函数应该是O（N）你这样做了。好了技术上将是O（N * M），其中M是分隔符的数量

修改1：

下面是一个变化，这将使它成为O（N）+ O（M），而不是O（N * M）：

而不是通过分隔符循环字符串中的每个字符，你应该通过事先的分隔符循环，并成立了一个这样的数组：

 布尔[] = isDelimiter新布尔[128]; //增加大小，如果您允许非ASCII 
的foreach（在isDelimiter字符DELIM）
 {
 isDelimiter [（int）的字符] =真; 
} 
  

然后，你可以使用这个数组来测试字符串的每个字符都在固定时间

I am doing a home work question to split a string without using the framework method.

Following is the working code I came up with.

I would like to know how can I improve the running time to O(n)?

Also any suggestions on improvement are welcome.

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);
}

解决方案

I have a few changes that will simultaneously make this function more C like and reduce the run time to O(n):

1) Instead of dynamically resizing your result array lots of times, you should create it with enough spots to hold the maximum number of strings (you know that number is less than txt.Length) and then resize it just once at the very end before returning it.

2) Instead of assembling your results with a StringBuilder, make a char[] buff of length txt.Length and an index variable j and do buff[j++] = txt[i].

I think your function should be O(N) after you do that. Well technically it will be O(N*M) where M is the number of delimiters.

EDIT 1:

Here is a change that will make it be O(N)+O(M) instead of O(N*M):

Instead of looping through the delimiters for each character in the string, you should loop through the delimiters in ADVANCE and set up an array like this:

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

Then you can just use this array to test each character of string in constant time.

这篇关于分割字符串没有string.Split的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！