17-Line Accepted C# DFS Solution


  • 3
    L
    public IList<string> AddOperators(string num, int target) {
        IList<string> result = new List<string>();
        dfs(result, "", 0, 0, num, target);
        return result;
    }
    private void dfs(IList<string> result, string curStr, long curSum, long curHead, string curNum, long target){
        if(curNum.Length == 0 && target - curSum - curHead == 0) result.Add(curStr);
        for(int i = 1; i < 11 && i <= curNum.Length; i++){
            string strNum = curNum.Substring(0, i); long lNum = Convert.ToInt64(strNum);
            if(lNum > int.MaxValue || curHead > int.MaxValue) break;
            if(curStr.Length == 0) dfs(result, strNum, 0, lNum, curNum.Substring(i), target);
            else{
                dfs(result, curStr + "*" + strNum, curSum, curHead * lNum, curNum.Substring(i), target);
                dfs(result, curStr + "+" + strNum, curSum + curHead, lNum, curNum.Substring(i), target);
                dfs(result, curStr + "-" + strNum, curSum + curHead, -lNum, curNum.Substring(i), target);
            }
            if(lNum == 0) break; // avoid result of "000"/"012" etc
        }
    }
    

    The first version accepted here.

    public IList<string> AddOperators(string num, int target) {
        IList<long> curList = new List<long>();
        IList<string> result = new List<string>();
        if(num.Length == 0) return result;
        for(int i = 1; i < 11 && i <= num.Length; i++){
            string curStr = num.Substring(0, i);
            if(Convert.ToInt64(curStr) <= int.MaxValue){
                curList.Add(Convert.ToInt64(curStr));
                dfs(result, curStr, curList, num.Substring(i), target);
                curList.RemoveAt(curList.Count - 1);
            }
            if(curStr == "0") break;
        }
        return result;
    }
    
    private void dfs(IList<string> result, string curStr, IList<long> curList, string curNum, long target){
        if(curNum.Length == 0){
            foreach(int i in curList) target -= i;
            if(target == 0) result.Add(curStr);
            return;
        }
        for(int i = 1; i < 11 && i <= curNum.Length; i++){
            string tmpNum = curNum.Substring(0, i);
            long lNum = Convert.ToInt64(tmpNum);
            if(lNum <= int.MaxValue){
                long tmp = curList[curList.Count - 1];
                curList[curList.Count - 1] *= lNum;
                if(Math.Abs(curList[curList.Count - 1]) <= int.MaxValue)
                    dfs(result, curStr + "*" + tmpNum, curList, curNum.Substring(i), target);
                curList[curList.Count - 1] = tmp;
    
                curList.Add(lNum);
                dfs(result, curStr + "+" + tmpNum, curList, curNum.Substring(i), target);
                curList[curList.Count - 1] = -lNum;
                dfs(result, curStr + "-" + tmpNum, curList, curNum.Substring(i), target);
                curList.RemoveAt(curList.Count - 1);
            }
            if(lNum == 0) break;
        }
    }

  • 0
    H

    Nice Job.
    But what will happen if lNum is greater than int.MaxValue ?

    For example num = "21474836482147483647" target = 1.
    We are expecting "2147483648-2147483647".
    However, your code will jump out since it is hitting the first break criteria.

    By the way, How can I delete one submitted code?
    I submit your code by mistake:(


  • 0
    L

    Hi HalforcNull, your case will not get answer by OJ too. I believe OJ has the same assumption of mine that each number element should be in scope of Integer, and more, the string is too long to solve in time on OJ so even OJ doesn't have an answer.

    This problem is not well defined for each number element's limitation, and if it's allowing big integer to be single element, we may need consider longer cases, but can't resolve it in OJ.

    If trying other solutions in discussion, you won't see any one can solve this case without time limit error too.

    I'm afraid you can't delete single submission, or you will need "manage session" to get a brand new clear session.


  • 0
    H

    That is the point. Seems like the people who made this question, didn't cover all possible input.
    As you said, more solutions had timeout issue. But, that only means they were breaking a non-functional requirement. They may break the non-functional requirement because the question is defective.
    In another hand, your code, is breaking a functional requirement. For my understanding, a functional requirement is important than a non-functional requirement.

    Anyway, good job. Thank you for your code and comment.


Log in to reply
 

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