Swift implementation with docs and full comments


  • 0
    M

    This is a variation on some solutions in this forum but written in Swift. This problem has a large number of permutations which I attempt to capture in the comments.

    class Solution {
        
        // Recursion 
        // - Parameters:
        //     - results: String array of valid math operation strings to return
        //     - result: String with current operation string being constructed
        //     - digits: Int array with the individual digits
        //     - target: Int with the target operation final value
        //     - offset: Current position in the digits array
        //     - mr:     MR like a calculator holding the result of the last operation
        //     - prior:  Special param to help multiplication which is backward looking due to order of operations (BOMDAS)
        func dfs(_ results: inout [String], _ result: String, _ digits: [Int], _ target: Int, _ offset: Int, _ mr: Int, _ prior: Int) {
            
            // if we're evaluated all the digits, we're at the end of the recrusion
            if offset == digits.count {
                // save the result string if the MR value equal to our target
                if target == mr {
                    results.append(result)
                }
                return
            }
            
            // walk the down digit array from the current offset
            for i in offset..<digits.count {
                // zeros are handled slightly differently
                // to account for 10, if we see a zero but we're not at the
                // current offset, we need to treat it like a 10
                // (the question is vague about this but it's in the examples)
                if i != offset && digits[offset] == 0 {
                    break
                }
    
                // build the current number from the digits
                var val = 0
                // i+1 is not bounded, so make sure we
                // don't exceed the digit array bounds
                for x in offset..<i+1 where x < digits.count {
                    // increase the existing value of val by a power of 10 on each iteration
                    val *= 10
                    val += digits[x]
                }
                
                // if we're at the first digit, there's no operation possible
                if offset == 0 {
                    // the first digit is simple, initialize the string and MR is digit
                    dfs(&results, result + String(val), digits, target, i + 1, val, val)
                } else {
                    // addition: add the digit to the string and add it to MR, track it in case we mul next
                    dfs(&results, result + "+" + String(val), digits, target, i + 1, mr + val, val)
                    // substraction: add the digit to the string and minus it from MR, track it in case we mul next
                    dfs(&results, result + "-" + String(val), digits, target, i + 1, mr - val, -val)
                    // multiplication: add the digit to the string, but we have an order of operations to deal with
                    // BOMDAS, so minus the prior value and add the multiplied value to MR, track the multiplied value in prior
                    dfs(&results, result + "*" + String(val), digits, target, i + 1, mr - prior + (prior * val), prior * val)
                }
            }
        }
        
        // the problem description is a bit vague, but we don't just
        // care about single digits, it's all possible numbers comprised 
        // of those digits, this greatly increases the number of permutations
        // to O(n^2)
        func addOperators(_ num: String, _ target: Int) -> [String] {
            var results: [String] = []
            
            // ensure we have evaluatble input
            if num.count == 0 {
                return results
            }
            
            // split the string into an array of digits
            let digits = Array(num).map({Int(String($0))!})
            
            // recurse from index zero
            dfs(&results, "", digits, target, 0, 0, 0)
            
            return results
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.