LeetCode - Delete and Earn

29 Dec 2017 • LeetCode

Question Definition

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

More …

LeetCode - Shortest Completing Word

28 Dec 2017 • LeetCode

Question Definition

Find the minimum length word from a given dictionary words, which has all the letters from the string licensePlate. Such a word is said to complete the given string licensePlate

Here, for letters we ignore case. For example, “P” on the licensePlate still matches “p” on the word.

It is guaranteed an answer exists. If there are multiple answers, return the one that occurs first in the array.

The license plate might have the same letter occurring multiple times. For example, given a licensePlate of “PP”, the word “pair” does not complete the licensePlate, but the word “supper” does.

More …

LeetCode - Repeated DNA Sequences

28 Dec 2017 • LeetCode

Question Definition

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: “ACGAATTCCG”. When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Java Solution

public List<String> findRepeatedDnaSequences(String s) {
    List<String> result = new LinkedList<>();
    Map<String, Integer> map = new HashMap<>();
    for(int i = 10; i <= s.length(); i++){
        String sub = s.substring(i - 10, i);
        if(map.containsKey(sub)){
            if(map.get(sub) == 1)
                result.add(sub);
            map.put(sub, map.get(sub) + 1);
        }else
            map.put(sub, 1);
    }
    return result;
}

LeetCode - Longest Word in Dictionary

28 Dec 2017 • LeetCode

Question Definition

Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

If there is no answer, return the empty string.

Example 1:

Input:
words = ["w","wo","wor","worl", "world"]
Output: "world"
Explanation:
The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Example 2:

Input:
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation:
Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

Note:

  1. All the strings in the input will only contain lowercase letters.
  2. The length of words will be in the range [1, 1000].
  3. The length of words[i] will be in the range [1, 30].

Java Solution

public String longestWord(String[] words) {
    Set<String> set = new HashSet<>();
    for(String word : words)
        set.add(word);
    String result = null;
    for(String word : words){
        String sub = "";
        boolean match = true;
        for(char c : word.toCharArray()){
            sub += c;
            if(!set.contains(sub)){
                match = false;
                break;
            }
        }
        if(match && (result == null || (word.length() > result.length()) || (word.length() == result.length() && word.compareTo(result) < 0)))
            result = word;
    }
    return result;
}