Please Help me to figure out why my code run so slow.


  • 0

    Bottom-up dynamic programming, time complexity is O(n) but actual run time only beast 1.5 % of people with 50ms.
    Are there anything can be improved in this code?

    Thanks!

    public int numDecodings(String s) {
            if (s.length() == 0 || s.charAt(0) == '0')return 0;
            int[] c = new int[s.length() + 1];
            c[0] = 1;
            c[1] = 1;
            for (int i = 2; i < s.length() + 1; i++){
                int lastTwo = Integer.parseInt(s.substring(i - 2, i));
                System.out.println(lastTwo);
                // special case if there are two 0 near with each other  
                if (s.charAt(i - 1) == s.charAt(i - 2) && s.charAt(i - 1) == '0')return 0;
                c[i] = (s.charAt(i - 1) != '0' ? c[i - 1] : 0) + (lastTwo <= 26 && lastTwo >= 10? c[i - 2] : 0);
            }
            return c[s.length()];
        }
    

Log in to reply
 

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