Concise Java Solution


  • 63
    • Construct char arrays from low.length() to high.length()
    • Add stro pairs from outside
    • When left > right, add eligible count
    private static final char[][] pairs = {{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
    
    public int strobogrammaticInRange(String low, String high) {
        int[] count = {0};
        for (int len = low.length(); len <= high.length(); len++) {
            char[] c = new char[len];
            dfs(low, high, c, 0, len - 1, count);
        }
        return count[0];
    }
    
    public void dfs(String low, String high , char[] c, int left, int right, int[] count) {
        if (left > right) {
            String s = new String(c);
            if ((s.length() == low.length() && s.compareTo(low) < 0) || 
                (s.length() == high.length() && s.compareTo(high) > 0)) {
                return;
            }
            count[0]++;
            return;
        }
        for (char[] p : pairs) {
            c[left] = p[0];
            c[right] = p[1];
            if (c.length != 1 && c[0] == '0') {
                continue;
            }
            if (left == right && p[0] != p[1]) {
                continue;
            }
            dfs(low, high, c, left + 1, right - 1, count);
        }
    }

  • 2
    W

    It's the easiest. Simple coding compared to equation-based method. Thanks!


  • 0
    M
    This post is deleted!

  • 7
    L

    Nice solution. I really like your clean and short solution. I get a c++ solution based on your idea.

    int strobogrammaticInRange(string low, string high) {
        map<char, char> mp = {{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
        int count = 0;
        for(int len = low.length(); len <= high.length(); len++) {
            string temp(len, '0');
             dfs(low, high, temp, 0, len - 1, count, mp);
        }
        return count;
    }
    void dfs(string low, string high, string str, int left, int right, int &count, map<char, char> &mp) {
        if(left > right) {
            if((str.length() == low.length() && str.compare(low) < 0) || 
               (str.length() == high.length() && str.compare(high) > 0)) return;
            count++; 
            return;
        }
        for(auto p : mp) {
            str[left] = p.first; 
            str[right] = p.second;
            if(str.size() != 1 && str[0] == '0') continue;
            if(left < right || left == right && p.first == p.second) dfs(low, high, str, left + 1, right - 1, count, mp);
        }
    }

  • 0
    X

    Thank you for sharing. I rewrite it in Python.

    '''

    count = 0
    pairs = ["00","11","69","88","96"]
    
    def strobogrammaticInRange(self, low, high):
        """
        :type low: str
        :type high: str
        :rtype: int
        """
        for i in range(len(low),len(high)+1):
            self.dfs(low,high,["#"]*i,0,i-1)
        return self.count
        
    def dfs(self,low,high,c,left,right):
        if left > right:
            s = "".join(c)
            if (len(s) == len(low) and int(s) < int(low)) or (len(s) == len(high) and int(s) > int(high)):
                return
            self.count += 1
            return
        for p in self.pairs:
            c[left] = p[0]
            c[right] = p[1]
            if len(c) != 1 and c[0] == "0":
                continue
            if left < right or (left == right and p[0] == p[1]):
                self.dfs(low,high,c,left+1,right-1)
    

    '''


  • 1
    C

    I think "if(c.length != 1 && c[0] == '0') continue;" should be "if(c.length != 1 && c[0] == '0' && left==0) continue;", because only outside 0 is not allowed. Did I miss anything? And also, is the complexity O(5^n*(n-m))?


  • 0
    This post is deleted!

  • 0

    hi, nice solution! i'm confused why we need to use count[0] here to record the result? actually i tried to use a normal int count to record the answer and it won't pass the test. So i'm just confused why this happened? did i miss something?


  • 0
    K

    @cpmvp The author of this solution is using the int array "count" as a container for the count int variable. It's actually not necessary to update the count this way; his dfs method could return 1 where he increments the count using ++, a local count variable could be used to sum the results of calling the dfs method recursively from within the for-loop, and that local count variable could be returned after the for-loop completes. The first call to the dfs method would then return the sum of all calls to the dfs method, which would still be an accurate count. But if we assume that the dfs method returns void, there needs to be a way to increment the count variable from within the body of the dfs method. This also could have been accomplished by making the count variable a global variable, but global variables are frowned upon. Using a container like the author did is another way that works, although in my personal opinion is not as elegant as the technique I described above.

    If you just pass an int, it will be passed by value (as are all function arguments in Java), and changing its value in the body of the function will have no effect on the variable that was used to pass that value into the function at the time the function was called. If my explanation wasn't enough for you, I recommend researching the concept of "pass by value." Good luck.


  • 0
    K

    @coldknight You might have missed something. c is the char array being used to build strings representing strobogrammatic numbers. c[0] will always be the first character of the string currently being built. The first character cannot be zero unless the number of digits in the strobogrammatic number we're currently trying to build is 1 (i.e. the length of c is 1). If the number of digits is 1, then the first digit is also the last digit, a number composed of a single digit where that digit is zero is the number zero, and zero is a strobogrammatic number.

    if(c.length != 1 && c[0] == '0') means "if the length isn't 1 and the first character is zero."

    if(c.length != 1 && c[0] == '0' && left==0) means "if the length isn't 1 and the first character is zero and we're currently deciding the value of the leftmost character in the string we're building." It's simply not necessary.

    However, I do believe an argument could be made for this:

    if(left==0 && c.length != 1 && c[0] == '0')

    so that the other two checks in the conditional expression are only executed when we're currently deciding the value of the leftmost character in the string we're building. Order matters in order to get the benefit of the short-circuiting boolean operators.


  • 0
    L

    @yavinci It's very concise solution and it could be better if you can change the following two points:

    1. Instead getting result from variable int[] count = {0}, let dfs() method return the count.
    2. Java naming convention. The static variable name should be upper case. pairs --> PAIRS.
      See detail below:
    public class Solution {
        private static final char[][] PAIRS = new char[][] {
            {'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
        public int strobogrammaticInRange(String low, String high) {
            if (low == null || high == null || low.length() > high.length()
                || (low.length() == high.length() && low.compareTo(high) > 0)) {
                return 0;
            }
            int count = 0;
            for (int len = low.length(); len <= high.length(); len++) {
                count += dfs(low, high, new char[len], 0, len - 1);
            }
            return count;
        }
        private int dfs(String low, String high, char[] ch, int left, int right) {
            if (left > right) {
                String s = new String(ch);
                if ((ch.length == low.length() && s.compareTo(low) < 0)
                    || (ch.length == high.length() && s.compareTo(high) > 0)) {
                    return 0;
                } else {
                    return 1;
                }
            }
            int count = 0;
            for (char[] p : PAIRS) {
                ch[left] = p[0];
                ch[right] = p[1];
                if (ch.length != 1 && ch[0] == '0') {
                    continue; //don't start with 0
                }
                if (left == right && (p[0] == '6' || p[0] == '9')) {
                    continue; //don't put 6/9 at the middle of string.
                }
                count += dfs(low, high, ch, left + 1, right - 1);
            }
            return count;
        }
    }
    

  • 0

    Why should we make sure that s.length() == low.length() or s.length() == high.length() when we decide whether new String is in range?

    if ((s.length() == low.length() && s.compareTo(low) < 0) || 
                (s.length() == high.length() && s.compareTo(high) > 0)) {
                return;
            }
    

    Hello all , I am confused by the lines above. Because I think String.compareTo() in java would consider about the length at first and then the unicode order according to Java api. However, after I remove the s.length() == low.length() or s.length() == high.length()
    It is wrong, I am really confused about this point. Someone to save me out of it?


Log in to reply
 

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