2015年11月4日星期三

Leetcode 247 Strobogrammatic Number II

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Find all strobogrammatic numbers that are of length = n.
For example,
Given n = 2, return ["11","69","88","96"].
Solution 1: back tracking to build all the numbers.
 public class Solution {  
   public List<String> findStrobogrammatic(int n) {  
     List<String> res=new ArrayList<>();  
     if (n<=0) return res;  
     char[] c=new char[n];  
     dfs(c,0,n-1,res);  
     return res;  
   }  
   private void dfs(char[] c, int i, int j, List<String> res) {  
     if (i>j) res.add(new String(c));  
     else {  
       if (i>0 || (i==0 && j==0)) {  
         c[i]='0';c[j]='0';  
         dfs(c,i+1,j-1,res);  
       }  
       if (i!=j) {  
         c[i]='6';c[j]='9';  
         dfs(c,i+1,j-1,res);  
         c[i]='9';c[j]='6';  
         dfs(c,i+1,j-1,res);  
       }  
       c[i]='1';c[j]='1';  
       dfs(c,i+1,j-1,res);  
       c[i]='8';c[j]='8';  
       dfs(c,i+1,j-1,res);  
     }  
   }  
 }  

没有评论:

发表评论