bool isMatch(const char *s, const char *p) {

        const char* star=NULL;

        const char* ss=s;

        while (*s){

            //advancing both pointers when (both characters match) or ('?' found in pattern)

            //note that *p will not advance beyond its length

            if ((*p=='?')||(*p==*s)){s++;p++;continue;} 

            // * found in pattern, track index of *, only advancing pattern pointer

            if (*p=='*'){star=p++; ss=s;continue;} 

            //current characters didn't match, last pattern pointer was *, current pattern pointer is not *

            //only advancing pattern pointer

            if (star){ p = star+; s=++ss;continue;} 

           //current pattern pointer is not star, last patter pointer was not *

           //characters do not match

            return false;

        }

       //check for remaining characters in pattern

        while (*p=='*'){p++;}

        return !*p;

    }

boolean comparison(String str, String pattern) {

        int s = 0, p = 0, match = 0, starIdx = -1;

        while (s < str.length()){

            // advancing both pointers

            if (p < pattern.length()  && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){

                s++;

                p++;

            }

            // * found, only advancing pattern pointer

            else if (p < pattern.length() && pattern.charAt(p) == '*'){

                starIdx = p;

                match = s;

                p++;

            }

           // last pattern pointer was *, advancing string pointer

            else if (starIdx != -1){

                p = starIdx + 1;

                match++;

                s = match;

            }

           //current pattern pointer is not star, last patter pointer was not *

          //characters do not match

            else return false;

        }

        //check for remaining characters in pattern

        while (p < pattern.length() && pattern.charAt(p) == '*')

            p++;

        return p == pattern.length();

}

def median(A, B):

    m, n = len(A), len(B)

    if m > n:

        A, B, m, n = B, A, n, m

    if n == 0:

        raise ValueError

    imin, imax, half_len = 0, m, (m + n + 1) / 2

    while imin <= imax:

        i = (imin + imax) / 2

        j = half_len - i

        if i < m and B[j-1] > A[i]:

            # i is too small, must increase it

            imin = i + 1

        elif i > 0 and A[i-1] > B[j]:

            # i is too big, must decrease it

            imax = i - 1

        else:

            # i is perfect

            if i == 0: max_of_left = B[j-1]

            elif j == 0: max_of_left = A[i-1]

            else: max_of_left = max(A[i-1], B[j-1])

            if (m + n) % 2 == 1:

                return max_of_left

            if i == m: min_of_right = B[j]

            elif j == n: min_of_right = A[i]

            else: min_of_right = min(A[i], B[j])

            return (max_of_left + min_of_right) / 2.0

private final String[] LESS_THAN_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};

private final String[] TENS = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};

private final String[] THOUSANDS = {"", "Thousand", "Million", "Billion"};

public String numberToWords(int num) {

    if (num == 0) return "Zero";

    int i = 0;

    String words = "";

    while (num > 0) {

        if (num % 1000 != 0)

            words = helper(num % 1000) +THOUSANDS[i] + " " + words;

        num /= 1000;

        i++;

    }

    return words.trim();

}

private String helper(int num) {

    if (num == 0)

        return "";

    else if (num < 20)

        return LESS_THAN_20[num] + " ";

    else if (num < 100)

        return TENS[num / 10] + " " + helper(num % 10);

    else

        return LESS_THAN_20[num / 100] + " Hundred " + helper(num % 100);

}

    // travel all the words combinations to maintain a window

    // there are wl(word len) times travel

    // each time, n/wl words, mostly 2 times travel for each word

    // one left side of the window, the other right side of the window

    // so, time complexity O(wl * 2 * N/wl) = O(2N)

    vector<int> findSubstring(string S, vector<string> &L) {

        vector<int> ans;

        int n = S.size(), cnt = L.size();

        if (n <=  || cnt <= ) return ans;

        // init word occurence

        unordered_map<string, int> dict;

        for (int i = ; i < cnt; ++i) dict[L[i]]++;

        // travel all sub string combinations

        int wl = L[].size();

        for (int i = ; i < wl; ++i) {

            int left = i, count = ;

            unordered_map<string, int> tdict;

            for (int j = i; j <= n - wl; j += wl) {

                string str = S.substr(j, wl);

                // a valid word, accumulate results

                if (dict.count(str)) {

                    tdict[str]++;

                    if (tdict[str] <= dict[str])

                        count++;

                    else {

                        // a more word, advance the window left side possiablly

                        while (tdict[str] > dict[str]) {

                            string str1 = S.substr(left, wl);

                            tdict[str1]--;

                            if (tdict[str1] < dict[str1]) count--;

                            left += wl;

                        }

                    }

                    // come to a result

                    if (count == cnt) {

                        ans.push_back(left);

                        // advance one word

                        tdict[S.substr(left, wl)]--;

                        count--;

                        left += wl;

                    }

                }

                // not a valid word, reset all vars

                else {

                    tdict.clear();

                    count = ;

                    left = j + wl;

                }

            }

        }

        return ans;

    }

int j = 0;

    for (int i = s.length() - 1; i >= 0; i--) {

        if (s.charAt(i) == s.charAt(j)) { j += 1; }

    }

    if (j == s.length()) { return s; }

    String suffix = s.substring(j);

    return new StringBuffer(suffix).reverse().toString() + shortestPalindrome(s.substring(0, j)) + suffix;