class Solution {
    private val map = mutableMapOf<String,List<Int>>()
    
    fun diffWaysToCompute(expression: String): List<Int> {
        if (map[expression] != null) {
            return map[expression]!!
        }
        
        val ans = mutableListOf<Int>()
        
        for(i in expression.indices) {
            if(expression[i] == '+' || expression[i] == '-' || expression[i] == '*') {
                val left = diffWaysToCompute(expression.substring(0,i))
                val right = diffWaysToCompute(expression.substring(i+1))
                
                for(j in left.indices) {
                    for(k in right.indices) {
                        when {
                            expression[i] == '+' -> ans.add(left[j] + right[k])
                            expression[i] == '-' -> ans.add(left[j] - right[k])
                            expression[i] == '*' -> ans.add(left[j] * right[k])
                        }
                    }
                }
            }
        }
        
        if(ans.isEmpty()) {
            ans.add(expression.toInt())
        }
        
        map[expression] = ans
        return ans
    }
}