Simple && accepted Swift 3, 39 ms / 83%


  • 0
    F

    This runs in 39ms on the OJ, faster than 83%. It's just a direct tree walk using caching to eliminate redundant searching.

    class Solution {
        func uniquePathsWithObstacles(_ obstacleGrid: [[Int]]) -> Int {
            let m = obstacleGrid.count
            guard m > 0 else {return 0}
            let n = obstacleGrid[0].count
            guard n > 0 else {return 0}
            var cache = Array(repeatElement(Array<Int?>(repeatElement(nil, count: n)), count: m))
    
            func inner(m m_ix: Int, n n_ix: Int) -> Int {
                if let v = cache[m_ix][n_ix] {
                    return v
                } else if obstacleGrid[m_ix][n_ix] > 0 {
                    cache[m_ix][n_ix] = 0
                    return 0
                } else if !(m_ix < m-1 && n_ix < n-1) { // On one or the other edge
                    let v: Int
                    if      m_ix < m-1 { v = inner(m: m_ix + 1, n: n_ix    ) }
                    else if n_ix < n-1 { v = inner(m: m_ix,     n: n_ix + 1) }
                    else {               v = 1 }
                    cache[m_ix][n_ix] = v
                    return v
                } else {
                    let ret = inner(m: m_ix + 1, n: n_ix) + inner(m: m_ix, n: n_ix + 1)
                    cache[m_ix][n_ix] = ret
                    return ret
                }
            }
    
            return inner(m: 0, n: 0)
        }
    }
    

Log in to reply
 

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