Hello Friends, can you please assist me with my implemeation to this leetcode question done in swift? I passes about 45 test cases out of 121.
You are given a string number representing a positive integer and a character digit.Return the resulting string after removingexactly one occurrenceof digit from number such that the value of the resulting string indecimalform ismaximized. The test cases are generated such that digit occurs at least once in number.
Example 1:
Input: number = "123", digit = "3" Output: "12" Explanation: There is only one '3' in "123". After removing '3', the result is "12".
Example 2:
Input: number = "1231", digit = "1" Output: "231" Explanation: We can remove the first '1' to get "231" or remove the second '1' to get "123". Since 231 > 123, we return "231".
Example 3:
Input: number = "551", digit = "5" Output: "51" Explanation: We can remove either the first or second '5' from "551". Both result in the string "51".
Constraints:
2 <= number.length <= 100
numberconsists of digits from '1'to '9'.
digitis a digit from '1'to '9'.
digitoccurs at least once in number.
Solution:
class Solution {
func removeDigit(_ number: String, _ digit: Character) -> String {
var number = number
var digit = digit
var result = ""
var removed = false
for char in number{
if char == digit && !removed{
removed = true
}
else{
result.append(char)
}
}
return result
}
}
Failed Test Case:
Input:
"133235"
"3"
Output:
"13235"
Expected:
"13325"
If we care about asymptotic complexity, where the input may be arbitrarily long with any number of occurrences of the given digit, then we can do this with a linear time algorithm:
Find the first occurrence of the given digit where the next digit after it has a larger value. (Note: if the given digit is the largest possible, ie. a 9 for decimal numbers, then this step can be skipped.)
If such a digit was found, remove it and return. (Note: if the found digit is immediately preceded by additional copies of the given digit, then any of them could be removed with the same result.)
Otherwise, remove the last occurrence of the given digit. (Note: same comment as in step 2.)
Not only does this avoid potentially quadratic work from re-parsing the whole number with each candidate digit removed, but it also allows inputs that would overflow the size of an integer.
Of course, if you want to use this approach yourself, then you’ll need to include comments explaining why it works. And I’m not going to write those for you.
Here is a simple, easy to verify, naive algorithm.
Delete each occurrence of the digit and collate the results. Then sort them in ascending order. The last value in the sorted results will be the answer.
Code
import Foundation
let numbers = ["126", "626", "676", "111611666", "111671666"]
let victim = Character ("6")
for number in numbers {
print (number, "...")
var candidates = [String] ()
for i in 0..<number.count {
var s = number
let deleted = s.removeIfExists (victim, at: i)
if deleted {
candidates.append (s)
}
}
if candidates.count > 0 {
candidates = candidates.sorted ()
for s in candidates {
print ("\t", s)
}
print ("--> answer:", candidates.last!)
}
}
// String.removeIfExists
// [https://forums.swift.org/t/how-to-delete-a-character-at-an-integer-index-from-a-string/61104/4]
//
extension String {
mutating func removeIfExists (_ character: Character, at offset: Int) -> Bool {
if let i = index (startIndex, offsetBy: offset, limitedBy: endIndex),
i < endIndex,
self [i] == character {
remove (at: i)
return true
}
else {
return false
}
}
}
Edit: This algorithm was already proposed by @cukr, but I have missed it.
The most efficient method that I can think of is go through the string from left to right and stop at each occurrence of the specified digit. If the digit to the right of the digit you stopped at is bigger than the digit, remove the digit you stopped at and you have the answer. This works because replacing the leftmost digit possible with a larger digit is guaranteed to be a bigger solution than changing anything in the less significant digits of the solution. If you get to the end of the string and the algorithm hasn't stopped, just remove the rightmost occurrence of the digit.
This solution is also a lot faster than the naive solution because it only requires 1 string operation and zero large integer string to integer conversions. The tests you're failing on may be tests where the input number is larger than a 64-bit integer, that's just a guess though.
If you're struggling to implement that I'm happy to help, but I'd rather not just give you a full implementation for the solution.
