My java recursive solution without helper function


  • 0
    U
    public class Solution {
        int k = -1;
        private List<String> insert(List<String> from, List<String> to){
            List<String> result = new ArrayList<String>();
            
            for(String a: to){
                final int mid = a.length() / 2;
                String[] parts = {a.substring(0, mid), a.substring(mid)};
                
                if(parts[0].charAt(0) == '0') continue;
                for(String b: from){
                    StringBuilder sb = new StringBuilder();
                    sb.append(parts[0]);
                    sb.append(b);
                    sb.append(parts[1]);
                    result.add(sb.toString());
                }
            }
            
            return result;
        }
        
        public List<String> findStrobogrammatic(int n) {
            k = k==-1?n:k;
            Set<String> set = new HashSet<String>();
            if(n == 1){
                return Arrays.asList("0", "1", "8");
            } else if(n == 2){
                if(k == 2){
                    return Arrays.asList("11","69","88","96");
                }
                return Arrays.asList("00","11","69","88","96");
            }
            
            List<String> result = new ArrayList<String>();
            
            for(int i = 1 ; i <= n/2 ; i++){
                int j = n - i;
                List<String> iresult = findStrobogrammatic(i);
                List<String> jresult = findStrobogrammatic(j);
                
                if(i%2 == 1 && j%2 == 1) continue;
                
                if(j%2 == 0){
                    for(String s: insert(iresult, jresult)){
                        set.add(s);   
                    }
                }else if(i%2 == 0){
                    for(String s: insert(jresult, iresult)){
                        set.add(s);
                    }
                }
            }
            
            return new ArrayList(set);
        }
    }
    

Log in to reply
 

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