Short Java DFS


  • 0
    V
        boolean toRet;
        public boolean isAdditiveNumber(String num) 
        {
            toRet = false;
            dfs(num, 0, 0, 0, 0);
            return toRet;
        }
        void dfs(String num, int lvl, long v1, long v2, int ind)
        {
            if(ind == num.length())
            {
                if(lvl > 2)
                    toRet = true;
                return;
            }
            long temp;
            for(int i = ind + 1; !toRet && i <= num.length() && i - ind < 11; i++)
            {
                if(num.charAt(ind) == '0' && i - ind > 1)
                    break;
                temp = Long.valueOf(num.substring(ind, i));
                if(lvl < 2 || ((v1 + v2) == temp))
                    dfs(num, lvl + 1, v2, temp, i);
            }
        }

Log in to reply
 

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