package com.fishercoder.solutions;

import java.util.HashMap;
import java.util.Map;

/**
 * A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.

Note:
Because the range might be a large number, the low and high numbers are represented as string.

*/
public class _248 {

    static class Solution2 {
        /**Credit: https://discuss.leetcode.com/topic/31386/concise-java-solution
         *
         Construct char arrays from low.length() to high.length()
         Add stro pairs from outside
         When left > right, add eligible count
         */

        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);
            }
        }
    }

    class Solution1 {
        Map<Character, Character> map = new HashMap<>();

        {
            map.put('1', '1');
            map.put('8', '8');
            map.put('6', '9');
            map.put('9', '6');
            map.put('0', '0');
        }

        String low = "";
        String high = "";

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

        private void strobogrammaticInRange(char[] arr, int[] count, int lo, int hi) {
            if (lo > hi) {
                String s = new String(arr);
                if ((arr[0] != '0' || arr.length == 1) && compare(low, s) && compare(s, high)) {
                    count[0]++;
                }
                return;
            }
            for (Character c : map.keySet()) {
                arr[lo] = c;
                arr[hi] = map.get(c);
                if ((lo == hi && c == map.get(c)) || lo < hi) {
                    strobogrammaticInRange(arr, count, lo + 1, hi - 1);
                }
            }
        }

        private boolean compare(String a, String b) {
            if (a.length() != b.length()) {
                return a.length() < b.length();
            }
            int i = 0;
            while (i < a.length() && a.charAt(i) == b.charAt(i)) {
                i++;
            }
            return i == a.length() ? true : a.charAt(i) <= b.charAt(i);
        }
    }
}

@@ -82,450 +82,8 @@
 p;%0A%0A
-/**%0A * A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).%0A%0AWrite a function to count the total strobogrammatic numbers that exist in the range of low %3C= num %3C= high.%0A%0AFor example,%0AGiven low = %2250%22, high = %22100%22, return 3. Because 69, 88, and 96 are three strobogrammatic numbers.%0A%0ANote:%0ABecause the range might be a large number, the low and high numbers are represented as string.%0A%0A*/%0A
 publ
@@ -102,16 +102,23 @@
 8 %7B%0A%0A   
+ public
  static 
@@ -131,17 +131,17 @@
 Solution
-2
+1
  %7B%0A     
@@ -1663,16 +1663,30 @@
  %7D%0A%0A    
+public static 
 class So
@@ -1683,33 +1683,33 @@
 c class Solution
-1
+2
  %7B%0A        Map%3CC

refactor 248