320. Generalized Abbreviation

For every step, treat it as a number and carry on or add the current number and add the former one

public class Solution {
    /** For each step we either keep the character or abbreviate it as a number **/
    public List<String> generateAbbreviations(String word) {
        List<String> res=new ArrayList<String>();
        generate(res,word,0,"",0);
        return res;
    }

    public void generate(List<String>res,String word,int pos,String cur,int num){ 
        if(pos == word.length()){
            if(num > 0)cur += num;
            res.add(cur);
            return;
         }
         //keep it as a number 
         generate(res,word,pos + 1,cur,num + 1);
         //keep it as itself and clear the current number and add the former one
         generate(res,word,pos + 1,cur+(num>0 ?num:"")+word.charAt(pos),0);
    }
}

301. Remove Invalid Parentheses

DFS的还没有实现

282. Expression Add Operatorsi

对于加和减 非常简单 乘法相对复杂 Record the previous value run time指数级

public class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> result = new ArrayList<String>();
        if(num==null||num.length()==0)return result;
        StringBuilder bd = new StringBuilder();
        helper(result,bd,num,0,target,0);
        return result;
    }
    public void helper(List<String> res,StringBuilder sub,String num,int index,long target,long pre){
        if(index == num.length() && target==0){
            res.add(sub.toString());
            return;
        }
        for(int i = index;i < num.length();i++){
            //所有连着的数字的情况,排除
            if(i != index && num.charAt(index) == '0') break;
            int len = sub.length();
            long cur = Long.parseLong(num.substring(index, i + 1));
            if(index == 0){
                helper(res,sub.append(cur),num,i+1,target-cur,cur);
                sub.setLength(len);
            }
            else{
                helper(res,sub.append("+").append(cur),num,i+1,target-cur,cur);
                sub.setLength(len);
                helper(res,sub.append("-").append(cur),num,i+1,target+cur,-cur);
                sub.setLength(len);
                helper(res,sub.append("*").append(cur),num,i+1,target-(pre*cur)+pre,pre*cur);
                sub.setLength(len);
            }
        }
    }
}

273. Integer to English Words

读的时候三位三位划分 每三位Thousand/Million进位 用Backtracking 处理每一小段然后和前面处理过的结合在一起 得到一个数字后几位用%10K 前面的相应是/10K

public class Solution {
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 index = 0;
        String res = "";
        while(num > 0){
            int left = num%1000;
            num = num/1000;
            if(left != 0)res = helper(left) + THOUSANDS[index] + " " + res;
            index++;
        }
        return res.trim();
    }

    //i是二位数字
    public 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);
    }
}