LeetCode Strobogrammatic Number II

原题链接在这里：https://leetcode.com/problems/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"].

题解：

base case 分奇数偶数两种. 拿到base case, 在每一个 string 前后加上"1", "1"; "8","8";...等等添加到新的res中去.

corner case是若是string长度大于1, "0"不能加在最前面. 所以用 m != n搞定.

Time Complexity: O(5^n), exponential.

Space: O(n/2 + 5^(n/2)), n/2层stack, 5^(n/2)是当前base的大小.

AC Java:

 public class Solution {

     public List<String> findStrobogrammatic(int n) {

         return findHelper(n, n);

     }

     private List<String> findHelper(int cur, int max){

         if(cur == 0){

             return new ArrayList<String>(Arrays.asList(""));

         }

         if(cur == 1){

             return new ArrayList<String>(Arrays.asList("0", "1", "8"));

         }

         List<String> res = new ArrayList<String>();

         List<String> base = findHelper(cur-2, max);

         for(String s : base){

             if(cur != max){

                 res.add("0" + s + "0");

             }

             res.add("1" + s + "1");

             res.add("8" + s + "8");

             res.add("6" + s + "9");

             res.add("9" + s + "6");

         }

         return res;

     }

 }

跟上Strobogrammatic Number III.

类似Strobogrammatic Number.

巴特西

LeetCode Strobogrammatic Number II

最新文章

热门文章