524. Longest Word in Dictionary through Deleting

Link

Solution

針對List每個String去判斷兩件事

1. 是否可以由d 生成 (isFormable?)

2. 是否比目前取得的最大string還長?

   1. 若string長度相等 那麼哪個lexicographical順序比較前面?

T: O(NK), N是d的長度，K是String s的長度，對每個list的string我們都最多go through過string s長度一次

  public String findLongestWord(String s, List<String> d) {
        String output = "";
        for(String string : d){
            if(output.length() <= string.length() &&
               isFormable(s, string) &&(
               string.length() > output.length() ||
               compare(string, output) > 0))
                {
                   output = string;    
                }
        }
        return output;
    }

    public boolean isFormable(String s, String input){
        int j = 0, i = 0;
        while( i < input.length() && j < s.length()){
            if(s.charAt(j) == input.charAt(i)){
                i++;
            }
            j++;
        }
        if(i == input.length()) return true;
        return false;
    }
    
    public int compare(String s1, String s2){
        for(int i = 0 ; i < s1.length() ; i++){
            if(s1.charAt(i) < s2.charAt(i)){
                return 1;
            }
            else if(s1.charAt(i) > s2.charAt(i)){
                return -1;
            }
        }
        return 0;
    }