Friday, May 18, 2018

Leetcode 412. Fizz Buzz

Write a program that outputs the string representation of numbers from 1 to n.
But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.
Example:
n = 15,

Return:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]



Code (java):
class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> ans = new ArrayList<>();
        
        if (n <= 0) {
            return ans;
        }
        
        for (int i = 1; i <= n; i++) {
            String s = "";
            
            if (i % 3 == 0) {
                s = "Fizz";
            }
            
            if (i % 5 == 0) {
                s += "Buzz";
            } else if (i % 3 != 0) {
                s = i + "";
            }
            
            ans.add(s);
        }
        
        return ans;
    }
}


Thursday, May 10, 2018

Leetcode 617. Merge Two Binary Trees

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
Example 1:
Input: 
 Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
      3
     / \
    4   5
   / \   \ 
  5   4   7
Note: The merging process must start from the root nodes of both trees.

Analysis:
The idea is just divide and conquer. 

Code (Java):
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return null;
        }
        
        TreeNode root = new TreeNode((t1 != null ? t1.val : 0) + (t2 != null ? t2.val : 0));
        
        root.left = mergeTrees(t1 != null ? t1.left : null, t2 != null ? t2.left : null);
        root.right = mergeTrees(t1 != null ? t1.right : null, t2 != null ? t2.right : null);
        
        return root;
    }
}

Tuesday, May 8, 2018

Leetcode 561. Array Partition I

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
Example 1:
Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
Note:
  1. n is a positive integer, which is in the range of [1, 10000].
  2. All the integers in the array will be in the range of [-10000, 10000].

Code (Java):
class Solution {
    public int arrayPairSum(int[] nums) {
        int sum = 0;
        
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length; i += 2) {
            sum += nums[i];
        }
        
        return sum;
    }
}

Thursday, May 3, 2018

Leetcode 771. Jewels and Stones

You're given strings J representing the types of stones that are jewels, and S representing the stones you have.  Each character in Sis a type of stone you have.  You want to know how many of the stones you have are also jewels.
The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".
Example 1:
Input: J = "aA", S = "aAAbbbb"
Output: 3
Example 2:
Input: J = "z", S = "ZZ"
Output: 0
Note:
  • S and J will consist of letters and have length at most 50.
  • The characters in J are distinct.

Code (Java):
class Solution {
    public int numJewelsInStones(String J, String S) {
        if (J == null || J.length() == 0 || S == null || S.length() == 0) {
            return 0;
        }
        
        int ans = 0;
        
        boolean[] dictS = new boolean[26];
        boolean[] dictL = new boolean[26];
        
        // step 1: pre-process the string J and put chars into the dict
        //
        for (int i = 0; i < J.length(); i++) {
            char c = J.charAt(i);
            if (c >= 'a' && c <= 'z') {
                dictS[c - 'a'] = true;
            } else {
                dictL[c - 'A'] = true;
            }
        }
        
        // step 2: check each char in S and see if it's in the dict
        //
        for (int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);
            if (c >= 'a' && c <= 'z' && dictS[c - 'a']) {
                ans++;
            } else if (c >= 'A' && c <= 'Z' && dictL[c - 'A']) {
                ans++;
            }
        }
        
        return ans;
    }
}


Tuesday, May 1, 2018

Leetcode 461. Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, calculate the Hamming distance.
Note:
0 ≤ xy < 231.
Example:
Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

The above arrows point to positions where the corresponding bits are different.

Code (Java):
class Solution {
    public int hammingDistance(int x, int y) {
        // step 1: get xor for x and y
        //
        int xorNum = x ^ y;
        
        // step 2: check how many bit 1s in the xorNum
        //
        int mask = 1;
        int distance = 0;
        
        
        for (int i = 0; i < 32; i++) {
            distance += xorNum & mask;
            xorNum = xorNum >> 1;
        }
        
        return distance;
    }
}


Sunday, April 29, 2018

Leetcode 1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Code (Java):
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] ans = new int[2];
        
        if (nums == null || nums.length < 2) {
            return ans;
        }
        
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int comp = target - nums[i];
            
            if (map.containsKey(comp)) {
                ans[0] = map.get(comp);
                ans[1] = i;
                break;
            } else {
                map.put(nums[i], i);
            }
        }
        
        return ans;
    }
}

Tuesday, April 24, 2018

Leetcode 809. Expressive Words

Sometimes people repeat letters to represent extra feeling, such as "hello" -> "heeellooo", "hi" -> "hiiii".  Here, we have groups, of adjacent letters that are all the same character, and adjacent characters to the group are different.  A group is extended if that group is length 3 or more, so "e" and "o" would be extended in the first example, and "i" would be extended in the second example.  As another example, the groups of "abbcccaaaa" would be "a", "bb", "ccc", and "aaaa"; and "ccc" and "aaaa" are the extended groups of that string.
For some given string S, a query word is stretchy if it can be made to be equal to S by extending some groups.  Formally, we are allowed to repeatedly choose a group (as defined above) of characters c, and add some number of the same character c to it so that the length of the group is 3 or more.  Note that we cannot extend a group of size one like "h" to a group of size two like "hh" - all extensions must leave the group extended - ie., at least 3 characters long.
Given a list of query words, return the number of words that are stretchy. 
Example:
Input: 
S = "heeellooo"
words = ["hello", "hi", "helo"]
Output: 1
Explanation: 
We can extend "e" and "o" in the word "hello" to get "heeellooo".
We can't extend "helo" to get "heeellooo" because the group "ll" is not extended.
Notes:
  • 0 <= len(S) <= 100.
  • 0 <= len(words) <= 100.
  • 0 <= len(words[i]) <= 100.
  • S and all words in words consist only of lowercase letters
Analysis:
The problem asks for a word in a list of words, it's stretchy if we can extend any character to the corresponding one in the S by repeating three or more times.

Code (Java):
class Solution {
    public int expressiveWords(String S, String[] words) {
        int ans = 0;
        for (String word : words) {
            if (isStretchy(S, word)) {
                ans++;
            }
        }
        
        return ans;
    }
    
    private boolean isStretchy(String s, String word) {
        int i = 0;
        int j = 0;
        int m = s.length();
        int n = word.length();
        
        while (i < m && j < n) {
            // Step 1: move j to the next group
            //
            while (i < m && j < n && s.charAt(i) == word.charAt(j)) {
                i++;
                j++;
            }
            
            // Step 2: move i to the next group
            //
            while (i > 0 && i < m && s.charAt(i) == s.charAt(i - 1)) {
                i++;
            }
            
            // Step 3: check if it's not stretchy
            //
            if (i < 3 || s.charAt(i - 1) != s.charAt(i - 2) || s.charAt(i - 2) != s.charAt(i - 3)) {
                break;
            }
        }
        
        return i == m && j == n;
    }
}

A better solution:
If we can pre-process the list of words and "cache" something, it will make the compare faster.

Monday, April 23, 2018

Leetcode 816. Ambiguous Coordinates

We had some 2-dimensional coordinates, like "(1, 3)" or "(2, 0.5)".  Then, we removed all commas, decimal points, and spaces, and ended up with the string S.  Return a list of strings representing all possibilities for what our original coordinates could have been.
Our original representation never had extraneous zeroes, so we never started with numbers like "00", "0.0", "0.00", "1.0", "001", "00.01", or any other number that can be represented with less digits.  Also, a decimal point within a number never occurs without at least one digit occuring before it, so we never started with numbers like ".1".
The final answer list can be returned in any order.  Also note that all coordinates in the final answer have exactly one space between them (occurring after the comma.)
Example 1:
Input: "(123)"
Output: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]
Example 2:
Input: "(00011)"
Output:  ["(0.001, 1)", "(0, 0.011)"]
Explanation: 
0.0, 00, 0001 or 00.01 are not allowed.
Example 3:
Input: "(0123)"
Output: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]
Example 4:
Input: "(100)"
Output: [(10, 0)]
Explanation: 
1.0 is not allowed.

Note:
  • 4 <= S.length <= 12.
  • S[0] = "(", S[S.length - 1] = ")", and the other elements in S are digits.

Code (Java):
class Solution {
    public List<String> ambiguousCoordinates(String S) {
        List<String> ans = new ArrayList<>();
        
        // step 1: split the string S into two halves, by inserting a comma
        //
        for (int i = 2; i <= S.length() - 2; i++) {
            List<String> leftCoordinates = findAllValidCoordinates(S.substring(1, i));
            List<String> rightCoordinates = findAllValidCoordinates(S.substring(i, S.length() - 1));
            
            for (String left : leftCoordinates) {
                for (String right : rightCoordinates) {
                    String s = '(' + left + ", " + right + ')';
                    ans.add(s);
                }
            }
        }
        
        return ans;
    }
    
    private List<String> findAllValidCoordinates(String s) {
        List<String> ans = new ArrayList<>();
        
        for (int i = 1; i <= s.length(); i++) {
            String left = s.substring(0, i);
            String right = s.substring(i, s.length());
            
            if ((left.equals("0") || !left.startsWith("0")) && !right.endsWith("0")) {
                String validString = i == s.length() ? left : left + '.' + right;
                ans.add(validString);
            }
        }
        
        return ans;
    }
}

Sunday, April 22, 2018

Leetcode 817. Linked List Components

We are given head, the head node of a linked list containing unique integer values.
We are also given the list G, a subset of the values in the linked list.
Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.
Example 1:
Input: 
head: 0->1->2->3
G = [0, 1, 3]
Output: 2
Explanation: 
0 and 1 are connected, so [0, 1] and [3] are the two connected components.
Example 2:
Input: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
Output: 2
Explanation: 
0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.
Note:
  • If N is the length of the linked list given by head1 <= N <= 10000.
  • The value of each node in the linked list will be in the range [0, N - 1].
  • 1 <= G.length <= 10000.
  • G is a subset of all values in the linked list.

Analysis:
Scanning through the list, if node.val is in G and node.next.val isn't (including if node.next is null), then this must be the end of a connected component.

Code (Java):
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int numComponents(ListNode head, int[] G) {
        Set<Integer> setG = new HashSet<>();
        
        // insert each number in G into the hash set
        //
        for (int num : G) {
            setG.add(num);
        }
        
        int numCC = 0;
        
        // Iterate all nodes in the linked list and get number of cc
        //
        while (head != null) {
            if (setG.contains(head.val) && 
                (head.next == null || !setG.contains(head.next.val))) {
                numCC++;
            }
            
            head = head.next;
        }
        
        return numCC;
     }
}

Leetcode 807. Max Increase to Keep City Skyline

In a 2 dimensional array grid, each value grid[i][j] represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can be different for different buildings). Height 0 is considered to be a building as well. 
At the end, the "skyline" when viewed from all four directions of the grid, i.e. top, bottom, left, and right, must be the same as the skyline of the original grid. A city's skyline is the outer contour of the rectangles formed by all the buildings when viewed from a distance. See the following example.
What is the maximum total sum that the height of the buildings can be increased?
Example:
Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output: 35
Explanation: 
The grid is:
[ [3, 0, 8, 4], 
  [2, 4, 5, 7],
  [9, 2, 6, 3],
  [0, 3, 1, 0] ]

The skyline viewed from top or bottom is: [9, 4, 8, 7]
The skyline viewed from left or right is: [8, 7, 9, 3]

The grid after increasing the height of buildings without affecting skylines is:

gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]

Notes:
  • 1 < grid.length = grid[0].length <= 50.
  • All heights grid[i][j] are in the range [0, 100].
  • All buildings in grid[i][j] occupy the entire grid cell: that is, they are a 1 x 1 x grid[i][j] rectangular prism.

Code (Java):
class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int num = grid.length;
        
        int ans = 0;
        
        int[] skylineTopBottom = new int[num];
        int[] skylineLeftRight = new int[num];
        
        // Step 1, get skyline from top and bottom, and from left and right
        //
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                skylineTopBottom[j] = Math.max(skylineTopBottom[j], grid[i][j]);
                skylineLeftRight[i] = Math.max(skylineLeftRight[i], grid[i][j]);
            }
        }
        
        // Step 2: scan the grid again and calculate the max height we can increase
        //
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                ans += Math.min(skylineTopBottom[j], skylineLeftRight[i]) - grid[i][j];
            }
        }
        
        return ans;
    }
}

Leetcode 788. Rotated Digits

X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X.  Each digit must be rotated - we cannot choose to leave it alone.
A number is valid if each digit remains a digit after rotation. 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other; 6 and 9 rotate to each other, and the rest of the numbers do not rotate to any other number and become invalid.
Now given a positive number N, how many numbers X from 1 to N are good?
Example:
Input: 10
Output: 4
Explanation: 
There are four good numbers in the range [1, 10] : 2, 5, 6, 9.
Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.
Note:
  • N  will be in range [1, 10000].

Solution:
Brute-force. Check each number from 1 to N and see if it's a good number.

Code (Java):
class Solution {
    public int rotatedDigits(int N) {
        int count = 0;
        
        for (int num = 1; num <= N; num++) {
            if (isGoodNumber(num)) {
                count++;
            }
        }
        
        return count;
    }
    
    private boolean isGoodNumber(int num) {
        boolean has2569 = false;
        while (num > 0) {
            int digit = num % 10;
            has2569 |= contains2569(digit);
            
            if (contains347(digit)) {
                return false;
            }
            num /= 10;
        }
        
        return has2569;
    }
    
    private boolean contains347(int digit) {
        if (digit == 3 || digit == 4 || digit == 7) {
            return true;
        }
        
        return false;
    }
    
    private boolean contains2569(int digit) {
        if (digit == 2 || digit == 5 || digit == 6 || digit == 9) {
            return true;
        }
        
        return false;
    }
}

Saturday, April 21, 2018

Leetcode 791. Custom Sort String

S and T are strings composed of lowercase letters. In S, no letter occurs more than once.
S was sorted in some custom order previously. We want to permute the characters of T so that they match the order that S was sorted. More specifically, if x occurs before y in S, then x should occur before y in the returned string.
Return any permutation of T (as a string) that satisfies this property.
Example :
Input: 
S = "cba"
T = "abcd"
Output: "cbad"
Explanation: 
"a", "b", "c" appear in S, so the order of "a", "b", "c" should be "c", "b", and "a". 
Since "d" does not appear in S, it can be at any position in T. "dcba", "cdba", "cbda" are also valid outputs.

Note:
  • S has length at most 26, and no character is repeated in S.
  • T has length at most 200.
  • S and T consist of lowercase letters only.

Analysis:
The problem is simply a merge sort. 

Code (Java):
class Solution {
    public String customSortString(String S, String T) {
        int[] dict = new int[26];
        
        for (int i = 0; i < dict.length; i++) {
            dict[i] = Integer.MAX_VALUE;
        }
        
        // Step 1: note the position of each char in S
        //
        for (int i = 0; i < S.length(); i++) {
            dict[S.charAt(i) - 'a'] = i;
        }
        
        // Step 2: merge sort
        //
        char[] Aux = new char[T.length()];
        char[] A = T.toCharArray();
        customMergeSort(dict, A, Aux, 0, A.length - 1);
        
        return String.copyValueOf(A);
    }
    
    private void customMergeSort(int[] dict, char[] A, char[] Aux, int lo, int hi) {
        
        if (lo >= hi) {
            return;
        }
        
        int mid = lo + (hi - lo) / 2;
        
        customMergeSort(dict, A, Aux, lo, mid);
        customMergeSort(dict, A, Aux, mid + 1, hi);
        
        customMerge(dict, A, Aux, lo, mid, hi);
    }
    
    private void customMerge(int[] dict, char[] A, char[] Aux, int lo, int mid, int hi) {
        for (int i = lo; i <= hi; i++) {
            Aux[i] = A[i];
        }
        
        int i = lo;
        int j = mid + 1;
        
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                A[k] = Aux[j++];
            } else if (j > hi) {
                A[k] = Aux[i++];
            } else if (dict[Aux[i] - 'a'] < dict[Aux[j] - 'a']) {
                A[k] = Aux[i++];;
            } else if (dict[Aux[i] - 'a'] >= dict[Aux[j] - 'a']) {
                A[k] = Aux[j++];
            }
        }
    }
}

A linear time solution:
class Solution {
    public String customSortString(String S, String T) {
        // Step 1: count the freq of each char in T
        //
        int[] freq = new int[26];
        
        for (int i = 0; i < T.length(); i++) {
            char c = T.charAt(i);
            freq[c - 'a']++;
        }
        
        // step 2: scan the string S and print the number of chars in T
        //
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);
            
            while (freq[c - 'a'] > 0) {
                sb.append(c);
                freq[c - 'a']--;
            }
        }
        
        // step 3: scan the freq again and append anything not zero
        //
        for (int i = 0; i < freq.length; i++) {
            while (freq[i] > 0) {
                sb.append((char) (i + 'a'));
                freq[i]--;
            }
        }
        
        return sb.toString();
    }
}

Friday, April 20, 2018

Leetcode 794. Valid Tic-Tac-Toe State

A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.
The board is a 3 x 3 array, and consists of characters " ""X", and "O".  The " " character represents an empty square.
Here are the rules of Tic-Tac-Toe:
  • Players take turns placing characters into empty squares (" ").
  • The first player always places "X" characters, while the second player always places "O" characters.
  • "X" and "O" characters are always placed into empty squares, never filled ones.
  • The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
  • The game also ends if all squares are non-empty.
  • No more moves can be played if the game is over.
Example 1:
Input: board = ["O  ", "   ", "   "]
Output: false
Explanation: The first player always plays "X".

Example 2:
Input: board = ["XOX", " X ", "   "]
Output: false
Explanation: Players take turns making moves.

Example 3:
Input: board = ["XXX", "   ", "OOO"]
Output: false

Example 4:
Input: board = ["XOX", "O O", "XOX"]
Output: true
Note:
  • board is a length-3 array of strings, where each string board[i] has length 3.
  • Each board[i][j] is a character in the set {" ", "X", "O"}

Analysis:
The problem only asks if the given board is valid. A board is valid only if 
1. number of X - number of O == 0
2. number of X - number of O == 1

If the number of X is equal to number of O, we need to check player X does not win. Otherwise,  player O must be less than player X.
If the number of X - number of O = 1, we need to check player O does not win. Otherwise, the game has stopped and player X cannot be greater than player O.

Code (Java):
class Solution {
    public boolean validTicTacToe(String[] board) {
        char[][] gameBoard = new char[3][3];
        
        for (int i = 0; i < 3; i++) {
            gameBoard[i] = board[i].toCharArray();
        }
        
        // Get number of X player and O player
        //
        int numOfX = 0;
        int numOfO = 0;
        
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                char c = gameBoard[i][j];
                
                if (c == 'X') {
                    numOfX++;
                } else if (c == 'O') {
                    numOfO++;
                }
            }
        }
        
        if (numOfX < numOfO || numOfX - numOfO > 1) {
            return false;
        }
        
        if (numOfX - numOfO == 1) {
            if (hasWon(gameBoard, 'O')) {
                return false;
            }
        }
        
        if (numOfX == numOfO) {
            if (hasWon(gameBoard, 'X')) {
                return false;
            }
        }
        
        return true;
    }
    
    private boolean hasWon(char[][] gameBoard, char player) {
        for (int i = 0; i < 3; i++) {
            if (gameBoard[i][0] == player && 
                gameBoard[i][1] == gameBoard[i][0] && 
                gameBoard[i][2] == gameBoard[i][1]) {
                return true;
            }
            
            if (gameBoard[0][i] == player && 
                gameBoard[1][i] == gameBoard[0][i] && 
                gameBoard[2][i] == gameBoard[1][i]) {
                return true;
            }
            
            if (player == gameBoard[0][0] && 
                gameBoard[0][0] == gameBoard[1][1] && 
                gameBoard[1][1] == gameBoard[2][2]) {
                return true;
            }
            
            if (player == gameBoard[0][2] && 
                gameBoard[1][1] == gameBoard[0][2] && 
                gameBoard[1][1] == gameBoard[2][0]) {
                return true;
            }
        }
        
        return false;
    }
}



Thursday, April 19, 2018

Leetcode 792. Number of Matching Subsequences

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.
Example :
Input: 
S = "abcde"
words = ["a", "bb", "acd", "ace"]
Output: 3
Explanation: There are three words in words that are a subsequence of S: "a", "acd", "ace".
Note:
  • All words in words and S will only consists of lowercase letters.
  • The length of S will be in the range of [1, 50000].
  • The length of words will be in the range of [1, 5000].
  • The length of words[i] will be in the range of [1, 50]

Brute Force Solution:
The most straight forward solution would be for each word in the words[], check with S and see if it's the subsequence of S. 

Code (Java):
class Solution {
    public int numMatchingSubseq(String S, String[] words) {
        int ans = 0;
        
        for (String word : words) {
            if (isSubsequence(S, word)) {
                ans++;
            }
        }
        
        return ans;
    }
    
    private boolean isSubsequence(String s, String w) {
        int sIndex = 0;
        int wIndex = 0;
        
        while (wIndex < w.length() && sIndex < s.length()) {
            if (s.charAt(sIndex) == w.charAt(wIndex)) {
                sIndex++;
                wIndex++;
            }
            else {
                sIndex++;
            }
        }
        
        return wIndex == w.length();
    }
}

Analysis:
The time complexity is O(S *(M + N)))
If we just compare two strings, the solution above is the best solution since we need to compare each character in the strings anyway. 

For this problem, however, since the length of the words is very big, it would be better if we can memorize something we did in the past.

A better solution (DP):

Monday, April 16, 2018

Leetcode 797. All Paths From Source to Target

Given a directed, acyclic graph of N nodes.  Find all possible paths from node 0 to node N-1, and return them in any order.
The graph is given as follows:  the nodes are 0, 1, ..., graph.length - 1.  graph[i] is a list of all nodes j for which the edge (i, j) exists.
Example:
Input: [[1,2], [3], [3], []] 
Output: [[0,1,3],[0,2,3]] 
Explanation: The graph looks like this:
0--->1
|    |
v    v
2--->3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
Note:
  • The number of nodes in the graph will be in the range [2, 15].
  • You can print different paths in any order, but you should keep the order of nodes inside one path.

Analysis:
A DFS for all the nodes should solve the problem.

Code (Java):
class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> ans = new ArrayList<>();
        
        if (graph == null || graph.length == 0) {
            return ans;
        }
        
        // DFS
        //
        List<Integer> path = new ArrayList<>();
        findPathToTarget(graph, 0, path, ans);
        
        return ans;
    }
    
    private void findPathToTarget(int[][] graph, int source, List<Integer> path, 
                                  List<List<Integer>> ans) {
        path.add(source);
        
        if (source == graph.length - 1) {
            List<Integer> cloneList = new ArrayList<>(path);
            ans.add(cloneList);
        }
        
        for (int neighbor : graph[source]) {
            findPathToTarget(graph, neighbor, path, ans);
        }
        
        path.remove(path.size() - 1);
    }
}


Complexity Analysis
  • Time Complexity: O(2^N N^2). We can have exponentially many paths, and for each such path, our prepending operation path.add(0, node) will be O(N^2).
  • Space Complexity: O(2^N N), the size of the output dominating the final space complexity.