查找字符串中字符之间的长度

Question

我有一个从字符和字符串到整数数组的函数。该数组有一个索引，它是该字符在文本中出现的次数内的一个数字，该索引的条目是与文本中出现的前一个字符的距离。如果该字符是换行符，则此函数基本上计算给定字符串的行长度数组。

val func: Char => (String => Array[Int]) = (ch: Char) => (str: String) => {
    var lens: Array[Int] = new Array[Int](20)
    var noCh: Int = 0
    var c: Int = 0 // accumlates till the next character is spotted
    for (i <- 0 until str.length) {
        c += 1
        if (str.charAt(i) == ch) {
            if (noCh>= lens.length) {
                val newlen: Array[Int] = new Array[Int](2*noCh)
                Array.copy(lens,0,newlen,0,noCh)
                lens = newlen
            }
            lens(noCh) = c; c = 0; noCh+= 1
        }
    }
    lens
    }                                         //> func  : Char => (String => Array[Int]) = <function1>
    func('\n')("hello world \n hello wstsadfasdf \n sdlfkjasdf\n")
                                                  //> res2: Array[Int] = Array(13, 20, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                                                  //| 0, 0, 0, 0)

有没有更快的方法解决这个问题？遍历每个字符似乎很慢，尤其是当您遍历一个非常大的字符串时。

Answer 1

该方法如何工作？通过神奇地预测下一个角色的位置？您可以构建一个排序集的映射来加速查询。 Build-time 仍然是 O(n)。但是可以在O(1).

中执行查询

Answer 2

正如其他人所说，需要扫描整个字符串。您还打算如何找到 ch 的出现？但你肯定是在制造恶劣的天气，因为它是 one-liner:

def func(ch:Char)(str:String):Array[Int] =
 str.foldLeft(List(1)){(a,c)=>if(c!=ch) a.head+1::a.tail else 1::a}.tail.reverse.toArray

func('\n')("hello world \n hello wstsadfasdf \n sdlfkjasdf\n")
//> res0: Array[Int] = Array(13, 20, 12)

或者（更简单，虽然在创建字符串数组时效率可能有点低）

def func2(ch:Char)(str:String):Array[Int] = str.split(ch).map(_.length+1)

查找字符串中字符之间的长度

Finding lengths between characters in a string

arrays

string

algorithm

scala

line