Generate all numbers under High value, and check if it is valid.


  • 0
    C
    Generate all related numbers less equal than high. Then comparison and validation. Please comment if you have better solution. 
    public class Solution {
            
            private HashMap<Integer, List<String>> mapByLen = new HashMap<Integer, List<String>>();
            private HashMap<String, String> map = new HashMap<String, String>();
            
            public int strobogrammaticInRange(String low, String high) {
                map.put("0", "0");
                map.put("1", "1");
                map.put("6", "9");
                map.put("8", "8");
                map.put("9", "6");
                int count = 0;
                if(low == null || low.length() == 0 || high == null || high.length() == 0) return 0;
               
                for(int i = low.length(); i <= high.length(); i++){
                    List<String> res = helper(i, i);
                    for(String s : res){
                        if(compare(low, s) <= 0 && compare(high, s) >= 0 && !isValid(s))
                             count++;
                    }
                   
                }
                
                return count;
                
            }
            
            private List<String> helper(int n, int m){
                
                if (m == 0) return new ArrayList<String>(Arrays.asList(""));
                if (m == 1) return new ArrayList<String>(Arrays.asList("0", "1", "8"));
                List<String> res = new ArrayList<String>();
                
                if(mapByLen.containsKey(m)){
                    return mapByLen.get(m);
                }
                
                List<String> list = helper(n, m - 2);
               
                for(int i = 0; i < list.size(); i++){
                    for(Map.Entry<String, String> e : map.entrySet()){
                        String num = e.getKey() + list.get(i) + e.getValue();
                        res.add(num);
                        
                    }
                    
                }
                mapByLen.put(m, res);
                return res;
            }
            
            private int compare(String a, String b){
                if(a.length() != b.length()){
                    return a.length() - b.length();
                }
                for(int i = 0; i < a.length(); i++){
                    if(a.charAt(i) != b.charAt(i)){
                        return a.charAt(i) - b.charAt(i);
                    }
                }
                return 0;
            }
            
            private boolean isValid(String s){
                if(s.length() <= 1) return false;
                if(s.charAt(0) == '0') return true;
                int count = 0;
                for(char c : s.toCharArray()){
                    if(c == '0') count++;
                }
                return count == s.length();
            }
        }

Log in to reply
 

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