0

我的任务是确定存在多少给定长度 N 的正确单词。只有那些在一行中没有任何重复字符序列的单词才被认为是正确的单词，我将在下面发布一个示例。Alafit 词由符号 a、b、c 组成。（小写）。我决定生成给定长度的所有字符组合。然后我编写了正确单词的搜索功能。代码正常工作。但我怀疑我的方法是否正确。也许我可以以某种方式优化这段代码，或者我应该使用其他方式来实现结果？

例子：

The specified word length: 3, the number of correct words: 12
        Correct words:
        ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"]

        Wrong words:
        ["aaa", "aab", "aac", "abb", "acc", "baa", "bba", "bbb", "bbc", "bcc", "caa", "cbb", "cca", "ccb", "ccc"]

我的代码：

import Foundation

func findRepetition(_ p: String) -> [String:Int] {
    var repDict: [String:Int] = [:]
    var p = p
    while p.count != 0 {
        for i in 0...p.count-1 {
            repDict[String(Array(p)[0..<i]), default: 0] += 1
        }
        p = String(p.dropFirst())
    }
    return repDict
}

var correctWords = [String]()
var wrongWords = [String]()
func getRepeats(_ p: String) -> Bool {
    let p = p
    var a = findRepetition(p)
    for i in a {
        var substring = String(Array(repeating: i.key, count: 2).joined())
        if p.contains(substring) {
            wrongWords.append(p)
            return false
        }
    }
    correctWords.append(p)
    return true
}

var counter = 0
func allLexicographicRecur (_ string: [String.Element], _ data: [String], _ last: Int, _ index: Int){
    var length = string.count-1
    var data = data
    for i in 0...length {
        data[index] = String(string[i])
        if index == last {
            if getRepeats(data.joined()) {
                counter += 1
            }
        }else{
            allLexicographicRecur(string, data, last, index+1)
        }

    }
}


func threeLanguage(_ l: Int) {
    var alphabet = "abc"
    var data = Array(repeating: "", count: l)
    allLexicographicRecur(alphabet.sorted(), data, l-1, 0)
    print("The specified word length: \(l), the number of correct words: \(counter)\n")
    print("Correct words:\n\(correctWords)\n")
    print("Wrong words:\n\(wrongWords)")
}


threeLanguage(3)

我也很难估计算法的复杂性（大 O）。因为目前该程序由复杂性不同的功能组成。有些有 O (n²)，有些有 O (n)。我也将非常感谢澄清这一点。

4

0 回答 0