748. Shortest Completing Word

Straightforward, but so many things can go wrong here. It’s important to clarify the requirement beforehand.

class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        int[] dict = new int[256];
        int size = 0;
        for (char c : licensePlate.toCharArray()) {
            if (Character.isLetter(c)) {
                dict[Character.toLowerCase(c)]++;
                size++;
            }
        }
        String res = "";
        for (String w : words) {
            if (w.length() < size) continue;
            int[] tmp = Arrays.copyOf(dict, dict.length);
            int cnt = 0;
            for (char c : w.toCharArray()) {
                if (tmp[c] > 0) cnt++;
                tmp[c]--;
            }
            if (cnt == size && (res.isEmpty() || w.length() < res.length())) {
                res = w;
            }
        }
        return res;
    }
}

583. Delete Operation for Two Strings

Similar to edit distance.
It’s important to initialise dp[x][0] and dp[0][x].

    public int minDistance(String word1, String word2) {
        if (word1.equals(word2)) return 0;
        else if (word1.isEmpty()) return word2.length();
        else if (word2.isEmpty()) return word1.length();
        
        int x = word1.length(), y = word2.length();
        int[][] dp = new int[x+1][y+1];
        
        for (int i = 1; i <= x; i++) dp[i][0] = i;
        for (int j = 1; j <= y; j++) dp[0][j] = j;

        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                char a = word1.charAt(i), b = word2.charAt(j);
                if (a == b) {
                    dp[i+1][j+1] = Math.min(dp[i][j], Math.min(dp[i][j+1]+1, dp[i+1][j]+1));
                } else {
                    dp[i+1][j+1] = Math.min(dp[i][j+1], dp[i+1][j]) + 1;
                } 
            }
        }
        return dp[x][y];
    }

Number to English

    def numberToWords(self, num):
        """
        :type num: int
        :rtype: str
        """
        DIGITS = ['', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine']
        TEENS = ['Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen']
        TENS = ['', '', 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety']
        BIGS = ['', 'Thousand', 'Million', 'Billion']
        result = ''
        big_index = 0
        if num == 0:
            return 'Zero'
        while num > 0:
            tmp = ''
            for i in range(3):
                if num == 0:
                    break
                val = num % 10
                num = num // 10
                if val == 0:
                    continue
                if i == 0:
                    tmp = DIGITS[val]
                elif i == 1:
                    if val == 1:
                        tmp = TEENS[DIGITS.index(tmp)]
                    else:
                        tmp = TENS[val] + ' ' + tmp if tmp else TENS[val]
                else:
                    tmp = DIGITS[val] + ' Hundred ' + tmp if tmp else DIGITS[val] + ' Hundred'

            if tmp:
                if BIGS[big_index]:
                    tmp += ' ' + BIGS[big_index]
                result = tmp + ' ' + result if result else tmp
            big_index += 1
        return result

Shortest Palindrome

Fast way -O(N)
用kmp在rev—s里面找s，其实就是找一个rev－s的后缀，这个后缀和s的一个前缀是一样的，这样删除那个后缀，就等于删除了duplicate，于是得到最短的palindrome

    def shortestPalindrome(self, s):
        size = len(s)
        if not size:
            return s
        next = [0 for x in range(size)]
        j = -1
        for i in range(size):
            if i == 0:
                next[i] = -1
            elif s[i] != s[j]:
                next[i] = j
            else:
                next[i] = next[j]
            while j >= 0 and s[i] != s[j]:
                j = next[j]
            j += 1

        rev_s = s[::-1]
        i = 0
        j = 0
        # find s in rev_s
        while i < size:
            while j >= 0 and rev_s[i] != s[j]:
                j = next[j]
            i += 1
            j += 1
        return rev_s[:size - j] + s

Slow way – O(N^2)
bcde -> [e]bcde -> [ed]bcde

    def shortestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        size = len(s)
        result = ""
        for i in range(size, -1, -1):
            result = s[i:size][::-1] + s
            if result == result[::-1]:
                break
        return result

Isomorphic String

Very hard for me.
Was thinking of counting letters.
Should simply check for mapping rules instead.

    def isIsomorphic(self, s, t):
        if len(s) != len(t):
            return False
        map = {}
        for i in range(len(s)):
            if (s[i] in map and map[s[i]] != t[i]
                or s[i] not in map and t[i] in map.values()):
                return False
            elif s[i] not in map:
                map[s[i]] = t[i]

        return True

Delete Digits to form min integer

两个问题：
1 数清楚index的位置
2 对于一切从str生成integer的 要检查leading 0.！

    public String DeleteDigits(String A, int k) {
        // write your code here
        int len = A.length();
        int rest = len - k;
        int index = 0;
        StringBuilder builder = new StringBuilder();
        while (rest > 0) {
            char min = (char)('9'+1);
            int pos = -1;
            for (; index <= len - rest; index++) {
                if (A.charAt(index) < min) {
                    min = A.charAt(index);
                    pos = index;
                }
            }
            builder.append(min);
            index = pos+1;
            rest--;
        }
        
        String result = builder.toString();
        index = 0;
        while (result.charAt(index) == '0') //!!!!!
            index++;
        return result.substring(index);
    }

Excel Sheet Column Title

注意index错位的情况。
1 -> A
2 -> B
3 -> C
…
26 -> Z
27 -> AA
28 -> AB

    public String convertToTitle(int n) {
        StringBuilder builder = new StringBuilder();
        while (n > 0) {
            char c = (char)((n-1)%26 + 'A');
            builder.insert(0, c);
            n = (n-1)/26;／／注意
        }
        return builder.toString();
    }

Largest Number

处理0+0的情况。
比较A+B的时候当作string 而不是 integer。

	public String largestNumber(int[] num) {
		StringBuilder result = new StringBuilder();
		String[] num2 = new String[num.length];
		for (int i = 0; i < num.length; i++)
			num2[i] = String.valueOf(num[i]);
		Arrays.sort(num2, new Comparator<String>() {
			@Override
			public int compare(String a, String b) {
				String A = a+b, B = b+a;
				return A.compareTo(B);
			}
		});
		int index = num.length - 1;
		while (index >= 0)
			result.append(num2[index--]);
		String res = result.toString();
		index = 0;
		while (index < res.length() && res.charAt(index) == '0')
		    index++;
		return index == res.length() ? "0" : res.substring(index);
	}

Substring with Concatenation of All Words

5个字符的单词们，
那么有5个外层开始循环的起始位置，对于内层循环，每次走5个字符。
依然是一个hashmap。更新map的编程题。

    public List<Integer> findSubstring(String S, String[] L) {
        List<Integer> result = new ArrayList<Integer>();
        if (L.length == 0 || S.length() == 0)
            return result;
        Map<String, Integer> map = new HashMap<String, Integer>();
        for (String str: L) {
            if (map.containsKey(str))
                map.put(str, map.get(str)+1);
            else
                map.put(str, 1);
        }
        int step = L[0].length(), window = L.length * step;
        for (int begin = 0; begin < step; begin++) { // step 个initial开始位置
            Map<String, Integer> has = new HashMap<String, Integer>();
            int count = 0, startIndex = begin;
            for (int index = begin; index <= S.length() - step; index+=step) { // <= inspect each step
                String word = S.substring(index, index+step);
                if (!map.containsKey(word)) {
                    startIndex = index + step;
                    count = 0;
                    has.clear();
                } else if (!has.containsKey(word)) {
                    has.put(word, 1);
                    count++;
                } else if (has.get(word) < map.get(word)) {
                    has.put(word, has.get(word)+1);
                    count++;
                } else if (has.get(word) == map.get(word) && word.equals(S.substring(startIndex, startIndex+step))) {
                    startIndex += step;
                } else if (has.get(word) == map.get(word)) {
                    startIndex = index + step;
                    count = 0;
                    has.clear();
                }
                
                if (count == L.length) {
                    result.add(startIndex);
                    String firstWord = S.substring(startIndex, startIndex+step);
                    has.put(firstWord, has.get(firstWord) - 1);
                    count--;
                    startIndex+=step;
                }
            }
        }
        return result;
	}

Minimum Window Substring

无它，就是两个hashmap：has 和 dict，就是需要写对。
数组写法容易写对，清晰; map API 太长。
需要反复更新string作为返回结果的，最好存index，便于高效返回substring

    public String minWindow(String S, String T) {
		String result = S + S;
		if (S.equals("") || T.equals(""))
			return "";
		int begin = 0, count = 0;
		int[] map = new int[256];
		int[] has = new int[256];
		int minB = -1, minE = S.length();
		
		for (Character c : T.toCharArray())
			map[c]++;
			
		for (int i = 0; i < S.length(); i++) {
			char cur = S.charAt(i);
			if (map[cur] != 0) {//found
                has[cur]++;
                
                if(map[S.charAt(i)] >= has[S.charAt(i)])
                    count++;
                
                if (count == T.length()) { 
                    while(map[S.charAt(begin)] == 0 || 
                    		map[S.charAt(begin)] < has[S.charAt(begin)]) {
                        if(map[S.charAt(begin)] < has[S.charAt(begin)]) {
                            has[S.charAt(begin)]--;
                        }
                        begin++;
                    }
                    if (i+1-begin < minE - minB) {
                        minE = i+1;
                        minB = begin;
                    }
                }
			}
		}
		if (minB == -1)
		    return "";
		return S.substring(minB, minE);
	}

public String minWindow(String S, String T) {
        int lenS = S.length(), lenT = T.length();
        if (lenS == 0 || lenS < lenT)
            return "";
            
        Map<Character, Integer> dict = new HashMap<Character, Integer>();
        Map<Character, Integer> has = new HashMap<Character, Integer>();
        char[] s = S.toCharArray();
        char[] t = T.toCharArray();
        
        for (char charInT: t) {
            if (dict.containsKey(charInT)) {
                dict.put(charInT, dict.get(charInT)+1);
            } else {
                dict.put(charInT, 1);
            }
        }
        
        String window = ""; 
        int begin = 0, curLen = 0, minB = -1, minE = -1; // store only index so that string is created only once
        
        for (int index = 0; index < lenS; index++) {
            char cur = s[index];
            if (dict.containsKey(cur)) {
                has.put(cur, has.containsKey(cur)? has.get(cur)+1: 1);
                if (has.get(cur) <= dict.get(cur)) // use length to test if qualify, much faster than comparing hashmaps
                    curLen++;
                if (curLen == lenT) {
                    while (begin < index && 
                        (!dict.containsKey(s[begin]) || has.get(s[begin]) > dict.get(s[begin]))) { 
                        if (dict.containsKey(s[begin]) && has.get(s[begin]) > dict.get(s[begin])) {
                            has.put(s[begin], has.get(s[begin])-1);
                        }
                        begin++;
                    }
                    if (minB == -1 || index - begin + 1 < minE - minB + 1) {
                        minB = begin;
                        minE = index;
                    }
                }
            }
        }
        if (minB == -1)
            window = "";
        else
            window = S.substring(minB, minE+1);
        return window;
	}