Swift 算法：如何获取包含所有子串且不重复的字符串

Question

假设您得到如下输入：

你好你好Swift 斯威苹果勒

（共 5 个）

我想要一个函数来接收上述输入和 return 字符串“helloSwiftApple”。 returning 字符串必须“包含”所有输入字符串而不重复。例如，returning 字符串不能是“hellohelloSwiftSwiApplele” 我如何用 Swift 做到这一点？

提前致谢，对于我的错误解释深表歉意。刚开始学习算法使用Swift.

Answer 1

这是一种有点“蛮力”的方法，但它可能对你有用。

将字符串拆分为一个数组 a 唯一“单词”
遍历数组for i in 0..<a.count
- 删除元素 i word
- a中是否有任何元素包含word？
- 如果否
  - 将word添加到新数组
- 将word放回a
return newArray 加入字符串

因此，我们可以使用此扩展程序从数组中删除重复项 (Hacking with Swift):

extension Array where Element: Hashable {
    func removingDuplicates() -> [Element] {
        var addedDict = [Element: Bool]()
        
        return filter {
            addedDict.updateValue(true, forKey: [=10=]) == nil
        }
    }
    
    mutating func removeDuplicates() {
        self = self.removingDuplicates()
    }
}

我们可以这样写一个函数：

func parseString(_ str: String) -> String {
    
    // split the string into an array of "words" (no spaces)
    var a1: [String] = str.components(separatedBy: " ").removingDuplicates()
    
    // an array to hold the unique words
    var a2: [String] = []
    
    // for each word
    for i in 0..<a1.count {
        // remove the word from the array
        let word = a1.remove(at: i)
        // filter the remaining array by elements containing word
        let n = a1.filter { [=11=].contains(word) }
        // if no elements contain word
        if n.count == 0 {
            // append it to array of unique words
            a2.append(word)
        }
        // put the word back into the full array
        a1.insert(word, at: i)
    }
    
    // change "-" to "" for no separators
    return a2.joined(separator: "-")
}

像这样的快速测试：

    let test: [String] = [
        "1 hello helloSwift Swi Apple le",
        "2 I want a string",
        "3 i want a string",
        "4 I want a function to receive the above inputs and return a String",
        "5 i want a function to receive the above inputs and return a String",
        "6 abc aBc Abc abc ABC aabc",
        "7 droid android otherdroid and android and otherdroid",
    ]

    test.forEach { s in
        let rs = parseString(s)
        print("Orig:", s)
        print("Ret :", rs)
        print()
    }

将此输出到调试控制台：

Orig: 1 hello helloSwift Swi Apple le
Ret : 1-helloSwift-Apple

Orig: 2 I want a string
Ret : 2-I-want-string

Orig: 3 i want a string
Ret : 3-want-string

Orig: 4 I want a function to receive the above inputs and return a String
Ret : 4-I-want-function-to-receive-the-above-inputs-and-return-String

Orig: 5 i want a function to receive the above inputs and return a String
Ret : 5-want-function-to-receive-the-above-inputs-and-return-String

Orig: 6 abc aBc Abc abc ABC aabc
Ret : 6-aBc-Abc-ABC-aabc

Orig: 7 droid android otherdroid and android and otherdroid
Ret : 7-android-otherdroid

您会立即注意到，您没有提到 case-sensitivity，所以我们没有解决这个问题...这就是示例 2 和 3 以及 4 和 5 return 不同结果的原因:

“我”不在“字符串”中找到
“i”是在“string”中找到

Swift 算法：如何获取包含所有子串且不重复的字符串

Swift Algorithm : how to get String that includes all substrings without repetition

algorithm

ios

swift