Swift: Evaluating if the letters in a String are contained within a longer String-CodePudding

Okay so my current code works, but I have a feeling it's incredibly inefficient. Essentially, I need to evaluate if a String contains the letters of a String that is shorter or the same length as the first one. (Imagine trying to use the letters that exist in Word A to spell a new word Word B. Word B can be shorter than Word A or the same length but has to only use the letters from Word A and cannot use the same letter twice.)

My current solution is to sort both strings into an array, then index each letter in the Word B array, check if it appears in the Word A array, then remove that character from the Word A array.

let wordOne = "battle"
let wordTwo = "table"

var wordOneSorted = wordOne.sorted()
var wordTwoSorted = wordTwo.sorted()


for letter in wordTwoSorted {
  if wordOneSorted.contains(letter) {
    print("Valid Letter")
    let idx = wordOneSorted.firstIndex(of:letter)
    wordOneSorted.remove(at: idx!)
  } else {
    print("Invalid Letter")
  }
}

Prints: Valid Letter Valid Letter Valid Letter Valid Letter Valid Letter

This works but it feels clunky and I wanted to see if I'm making a simple task more complicated than I need it to be. I only need an evaluation of the entire comparison, if all the leters work than "True" and if at least one is invalid than "False".

Thank you!

CodePudding user response：

Your code can give a simple good/bad response as follows:

let wordOne = "battle"
let wordTwo = "table"

var letters = wordOne
var good = true
for letter in wordTwo {
  if letters.contains(letter) {
    let idx = letters.firstIndex(of:letter)
    letters.remove(at: idx!)
  } else {
    good = false
    break
  }
}
print(good ? "Good" : "Bad")

There's no need to sort the letters of each word. That doesn't make this approach any more efficient. I add the var letters just so the value can be modified as the loop runs.

Here's an alternate approach using NSCountedSet. This isn't a pure Swift class but is provided by Foundation.

let wordOne = "battle"
let wordTwo = "table"

let set1 = NSCountedSet(array: Array(wordOne))
let set2 = NSCountedSet(array: Array(wordTwo))
let extra = set2.filter { set2.count(for: $0) > set1.count(for: $0) }
print(extra.isEmpty ? "Good" : "Bad")

NSCountedSet is a subclass of Set (really of NSSet and NSMutableSet) that adds a count for each element in the set.

The filter makes sure there are enough of each letter. Anything left in extra means wordTwo had more instances of a letter than in wordOne.

CodePudding user response：

I was wondering how I would, and here is an alternative. It's good to have different ways of thinking an issue.

We create a [Character: (Int, Int)] where - keys will be the letter, and first tuple value the number of occurences in str1, and second tuple value the number of occurrences in str2.
Then, we check if all values present in str1 have at leas the same number of occurrences that in str2.

var counter: [Character: (Int, Int)] = [:]
counter = str1.reduce(counter) {
    var values = $0
    var tuple: (Int, Int) = $0[$1, default: (0, 0)]
    values[$1] = (tuple.0   1, tuple.1)
    return values
}
counter = str2.reduce(counter) {
    var values = $0
    var tuple: (Int, Int) = $0[$1, default: (0, 0)]
    values[$1] = (tuple.0, tuple.1   1)
    return values
}
let doesInclude = counter.allSatisfy { _, tuple in
    tuple.0 >= tuple.1
}
print("\(str1) includes all letters from \(str2): \(doesInclude)")

The value of counter for "abc" vs "cde":

["d": (0, 1), "b": (1, 0), "c": (1, 1), "e": (0, 1), "a": (1, 0)]

The value of counter for "battle" vs "table":

["t": (2, 1), "e": (1, 1), "a": (1, 1), "b": (1, 1), "l": (1, 1)]

CodePudding user response：

I like @HangarRash answer, but you could also use sort to your advantage, i.e. when letters are sorted you can move in both arrays simultaneously and stop as soon as the first difference was found (no need to remove anything):

func isContained(in word1: String, word word2: String) -> Bool {
    
    var word1Sorted = word1.sorted()
    var word2Sorted = word2.sorted()
    
    var c1 = word1Sorted.count - 1
    var c2 = word2Sorted.count - 1
    
    while c2 >= 0 && c1 >= 0 {
        
        if word1Sorted[c1] == word2Sorted[c2] {
            // Found a match - advance to next character in both arrays
            print("Valid Letter \(word2Sorted[c2])")
            c1 -= 1
            c2 -= 1
        } else if word1Sorted[c1] > word2Sorted[c2] {
            // Ignoring a letter present in wordOne, but not wordTwo
            print("Skipping Letter \(word1Sorted[c1])")
            c1 -= 1
        } else { // wordOneSorted[c1] < wordTwoSorted[c2]
            // the letter was not found in wordOneSorted - no need to continue
            print("Invalid Letter \(word2Sorted[c2])")
            return false
        }
    }
    
    // If we finished the loop then the result is:
    // - We've got to the beginning of word2, meaning we found all letters of it in word1
    // - Or we've got to the beginning of word1, meaning not all letters of word 2 were found
    return c2 < 0
}

So for example:

let wordOne = "battle"
let wordTwo = "table"

let good = isContained(in: wordOne, word: wordTwo)
print(good ? "Good" : "Bad")

will run on entire array (of the Word 2 at least):

Valid Letter t
Skipping Letter t
Valid Letter l
Valid Letter e
Valid Letter b
Valid Letter a
Good

While if there's a difference, e.g.

let wordOne = "battle"
let wordTwo = "tables"

let good = isContained(in: wordOne, word: wordTwo)
print(good ? "Good" : "Bad")

it may exit much faster:

Valid Letter t
Skipping Letter t
Invalid Letter s
Bad