BiruLyu
8/5/2017 - 6:35 PM

## 248. Strobogrammatic Number III(#).java

``````public class Solution {
private int compare(String s1, String s2) {
if (s1.length() < s2.length()) return -1;
else if (s1.length() > s2.length()) return 1;
for (int i = 0; i < Math.min(s1.length(), s2.length()); i++) {
if (s1.charAt(i) < s2.charAt(i)) return -1;
else if (s1.charAt(i) > s2.charAt(i)) return 1;
}
return 0;
}
private int count;
private final char[] pairs = {'0', '0', '1', '1', '6', '9', '8', '8', '9', '6'};
private void helper(char[] nums, int start, int end, String low, String high, boolean lowerlimit, boolean upperlimit) {
if (start > end) {
String s = new String(nums);
if ((!lowerlimit || compare(s, low) >= 0) && (!upperlimit || compare(s, high) <= 0)) count++;
return;
}
for (int i = 0; i < 10; i += 2) {
if (start == end && pairs[i] != pairs[i+1]) continue;
nums[start] = pairs[i];
nums[end] = pairs[i+1];
if (start == 0 && nums[start] == '0' && nums.length > 1) continue;
if (upperlimit && compare(new String(nums, 0, start+1), high.substring(0, start+1)) > 0) break;
if (lowerlimit && compare(new String(nums, 0, start+1), low.substring(0, start+1)) < 0) continue;
helper(nums, start+1, end-1, low, high, lowerlimit, upperlimit);
}
}
public int strobogrammaticInRange(String low, String high) {
if (compare(low, high) > 0) return 0;
int n = low.length(), m = high.length(), result = 0;
count = 0;
if (m == n) {
helper(new char[m], 0, m-1, low, high, true, true);
result += count;
} else {
helper(new char[n], 0, n-1, low, high, true, false);
result += count;
count = 0;
helper(new char[m], 0, m-1, low, high, false, true);
result += count;
}
int even = 1, odd = 3;
for (int i = 2; i < m; i++) {
if (i > n && i < m) result += i%2 == 0 ? even*4 : odd*4;
if (i%2 ==0) even = even*5;
else odd = odd*5;
}
return result;
}
}``````
``````public class Solution {
public int strobogrammaticInRange(String low, String high) {
int res=0;
if(low.length()>high.length()) return 0;
for (int i = low.length(); i <high.length() ; i++) {
res+=strbgWithDigits(i, false);
}
res+=strbgWithSameDigitsBelow(high, false);
res-=strbgWithSameDigitsBelow(low, false);
if(isStb(low)) res++;
return res;
}

private boolean isStb(String low) {
if(low.length()==0) return true;
for (int i = 0; i <= low.length()/2; i++) {
if(!isPair(low.charAt(i),low.charAt(low.length()-i-1))) return false;
}
return true;
}

private boolean isPair(char c, char c1) {
if(c=='1') return c1=='1';
if(c=='0') return c1=='0';
if(c=='8') return c1=='8';
if(c=='6') return c1=='9';
if(c=='9') return c1=='6';
return false;
}

private int strbgWithSameDigitsBelow(String num, boolean can0Initial) {
int res=0;
if(num.length()==0){
return 1;
}
if(num.length()==1) {
int temp=1;
if(num.charAt(0)>='1') temp++;
if(num.charAt(0)>='8') temp++;
return temp;
}
if(can0Initial && num.charAt(0)>'0') {
res+=strbgWithDigits(num.length()-2,true);
}
if(num.charAt(0)>'1') {
res+=strbgWithDigits(num.length()-2,true);
}
if(num.charAt(0)>'6') {
res+=strbgWithDigits(num.length()-2,true);
}
if(num.charAt(0)>'8'){  //==9
res+=strbgWithDigits(num.length()-2,true);
res+=strbgWithSameDigitsBelow(num.substring(1,num.length()-1),true);
if(isStb(num.substring(1,num.length()-1)) && num.charAt(num.length()-1)<'6') {
res--;
}
}
if(num.charAt(0)=='1'||num.charAt(0)=='8') {
res+=strbgWithSameDigitsBelow(num.substring(1,num.length()-1),true);
if(isStb(num.substring(1,num.length()-1)) && num.charAt(num.length()-1)<num.charAt(0)) {
res--;
}
}
if(num.charAt(0)=='6') {
res+=strbgWithSameDigitsBelow(num.substring(1,num.length()-1),true);
if(isStb(num.substring(1,num.length()-1)) && num.charAt(num.length()-1)<'9') {
res--;
}
}
if(num.charAt(0)=='0'&& can0Initial) {
res+=strbgWithSameDigitsBelow(num.substring(1,num.length()-1),true);
}

return res;
}

private int strbgWithDigits(int d, boolean can0Initial) {
if(d<=0) return 1;
if(d==1) return 3;
int res=4;
if(can0Initial) {
res=5;
}
for (int i = 1; i <d-1-i ; i++) {
res*=5;
}
if(d%2==1) res*=3;
return res;
}
}``````
``````public class Solution {
private static final char[][] pairs = {{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};

public int strobogrammaticInRange(String low, String high) {
int[] count = {0};
for (int len = low.length(); len <= high.length(); len++) {
char[] c = new char[len];
dfs(low, high, c, 0, len - 1, count);
}
return count[0];
}

public void dfs(String low, String high , char[] c, int left, int right, int[] count) {
if (left > right) {
String s = new String(c);
if ((s.length() == low.length() && s.compareTo(low) < 0) ||
(s.length() == high.length() && s.compareTo(high) > 0)) {
return;
}
count[0]++;
return;
}
for (char[] p : pairs) {
c[left] = p[0];
c[right] = p[1];
if (c.length != 1 && c[0] == '0') {
continue;
}
if (left == right && p[0] != p[1]) {
continue;
}
dfs(low, high, c, left + 1, right - 1, count);
}
}
}``````