查找给定的字符串是使用scala的另一个字符串的子字符串的多少次

问题描述：

查找给定的字符串是使用scala的另一个字符串的子字符串的次数的优雅方式是什么？查找给定的字符串是使用scala的另一个字符串的子字符串的多少次

下面的测试用例应该清楚什么要求：

import org.scalatest.FunSuite 

class WordOccurrencesSolverTest extends FunSuite { 

    private val solver = new WordOccurrencesSolver() 

    test("solve for a in a") { 
    assert(solver.solve("a", "a") === 1) 
    } 

    test("solve for b in a") { 
    assert(solver.solve("b", "a") === 0) 
    } 

    test("solve for a in aa") { 
    assert(solver.solve("a", "aa") === 2) 
    } 

    test("solve for b in ab") { 
    assert(solver.solve("b", "ab") === 1) 
    } 

    test("solve for ab in ab") { 
    assert(solver.solve("ab", "ab") === 1) 
    } 

    test("solve for ab in abab") { 
    assert(solver.solve("ab", "abab") === 2) 
    } 

    test("solve for aa in aaa") { 
    assert(solver.solve("aa", "aaa") === 2) 
    } 
}

这里是我的解决方案，而我是不是特别自豪的问题：

class WordOccurrencesSolver { 

    def solve(word: String, text: String): Int = { 
    val n = word.length 
    def solve(acc: Int, word: String, sb: String): Int = sb match { 
     case _ if sb.length < n => acc 
     case _ if sb.substring(0, n) == word => solve(acc + 1, word, sb.tail) 
     case _ => solve(acc, word, sb.tail) 
    } 
    solve(0, word, text) 
    } 

}

我假设有一定成为一个干净的一行，它利用了Scala的高阶函数而不是递归和匹配/ case子句。

那么......我会建议你远离寻找一条衬里的诱惑。首先尝试着重于解决方案的“时间复杂性”。只有在照顾到这一点之后，才能寻找单行或高雅。试着想一个避免使用子字符串（这实际上是O（n））的时间使用的解决方案，使得你的解决方案的性能非常差。 –

类似的'.tail'对于String也是O（n），应该避免。 –

好点，我错过了它。 – GA1

答

在关键字的出现次数的数量sliding来创建滑动窗口迭代器并计算与目标字符串相等的wondows。

该解决方案在功能上同样为您提供了可接受的性能。

def countOccurrences(src: String, tgt: String): Int = 
    src.sliding(tgt.length).count(window => window == tgt)

看起来不错。这个解决方案的时间复杂度是多少？ – GA1

那么......可以说你的'src'长度是'm'，'tgt'长度是'n'。然后第1步 - 创建窗口迭代器是'O（m）'。这个迭代器将会有'm-n'个窗口字符串。步骤2 - count为每个窗口字符串比较长度为'n'的窗口字符串与'tgt'字符串。所以它是'O（n * m）'。所以所有的互补性都是'O（m * n）' –

太好了，这正是我想要找到的解决方案。但我仍然很好奇。在符号后面的'O（n）'中是否有算法可以实现同样的事情（不一定是一行）？这就是'src'长度不相关的算法，用'O'来表示。 – GA1

答

你或许可以用这个Java函数：

StringUtils.countMatches(stringToFindMatchesIn, keyWordToFind);

如果你正在寻找一个惯用的Scala的解决方案，那么你可以使用这将返回字符串

我不认为OP被允许使用。这看起来像一个家庭作业问题/练习。 –

查找给定的字符串是使用scala的另一个字符串的子字符串的多少次

相关推荐