247. Strobogrammatic Number II
文章目录
247. Strobogrammatic Number II
题目链接:https://leetcode.com/problems...
这题recursion和iteration都可以做,一种思路就是从中间开始往两边延伸,每次c[i-k], c[i+k]有5种可能性: (6, 9), (9, 6), (1, 1), (8, 8)和(0, 0),其中开头处不能是0。可以加memo或者用dp table优化。
public class Solution {
public List<String> findStrobogrammatic(int n) {
List<String> dp = new ArrayList();
if(n % 2 == 1) {
dp.add("0"); dp.add("1"); dp.add("8");
}
else dp.add("");
if(n <= 1) return dp;
// get permutation of (0, n/2)
String[] numbers = new String[] {"0", "1", "6", "8", "9"};
String[] reverse = new String[] {"0", "1", "9", "8", "6"};
for(int i = n / 2 - 1; i >= 0; i--) {
List<String> temp = new ArrayList();
for(String s : dp) {
if(i != 0) temp.add(numbers[0] + s + reverse[0]);
for(int j = 1; j < numbers.length; j++) {
temp.add(numbers[j] + s + reverse[j]);
}
}
dp = temp;
}
return dp;
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论