查找給定的字符串是使用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子句。

來源

2017-04-10 GA1

那麼......我會建議你遠離尋找一條襯裏的誘惑。首先嚐試着重於解決方案的「時間複雜性」。只有在照顧到這一點之後，才能尋找單行或高雅。試着想一個避免使用子字符串（這實際上是O（n））的時間使用的解決方案，使得你的解決方案的性能非常差。 –

類似的'.tail'對於String也是O（n），應該避免。 –

好點，我錯過了它。 – GA1

在關鍵字的出現次數的數量sliding來創建滑動窗口迭代器並計算與目標字符串相等的wondows。

該解決方案在功能上同樣爲您提供了可接受的性能。

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

來源

2017-04-10 13:09:07

看起來不錯。這個解決方案的時間複雜度是多少？ – 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的解決方案，那麼你可以使用這將返回字符串

來源

2017-04-10 12:54:32 iPhantomGuy

我不認爲OP被允許使用。這看起來像一個家庭作業問題/練習。 –

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

回答

相關問題