[LeetCode] Combination Sum III

Problem: Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

• Only numbers 1 through 9 are used.
• Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

Approach: We can use backtracking here. The recursive relation would be something like below:

f(k, n, i) = f(k - 1, n - i, i - j), where j is (i + 1)....9

Implementation in C#:

    public IList<IList<int>> CombinationSum3(int k, int n)

    {

        var currNums = new List<int>();

        var result = new List<IList<int>>();

        this.CombinationSum(k, n, currNums, 1, result);

        return result;

    }

    private void CombinationSum(int k,

                                int n,

                                List<int> currNums,

                                int currNum,

                                List<IList<int>> result)

    {

        if (currNums.Count == k)

        {

            if (n == 0)

            {

                Console.WriteLine($"Adding {string.Join(", ", currNums)}");

                result.Add(new List<int>(currNums));

            }

            return;

        }

        for (int i = currNum; i <= 9; ++i)

        {

            if (n - i >= 0)

            {

                currNums.Add(i);

                this.CombinationSum(k, n - i, currNums, i + 1, result);

                currNums.RemoveAt(currNums.Count - 1);

            }

            else

            {

                break;

            }

        }

    }

Complexity: O(2 ^ 9)

[LeetCode] Word Search II

Problem: Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

Approach: The problem is similar to the problem of search a word in a matrix except here we are given an array of words. We will have the similar backtracking approach here too but we will use Trie to make it more efficient.

Implementation:

public class TrieNode

{

    public const short ALPHABET_SIZE = 26;

    public TrieNode(char value)

    {

        this.Value = value;

        this.Children = new TrieNode[ALPHABET_SIZE];

        this.End = 0;

    }

    public char Value { get; set; }

    public TrieNode[] Children { get; set; }

    public string Word { get; set; }

    public int End { get; set; }

}

public class Trie

{

    public Trie()

    {

        this.root = new TrieNode('/'); // special charater for root

    }

    public void Insert(string word)

    {

        TrieNode node = root;

        foreach(char ch in word)

        {

            if (node.Children[ch - 'a'] == null)

            {

                node.Children[ch - 'a'] = new TrieNode(ch);

            }

            node = node.Children[ch - 'a'];

        }

        node.End++;

        node.Word = word;

    }

    

    public void SearchOnBoard(char[][] board, int i, int j, List<string> result)

    {

        if (this.root.Children[board[i][j] - 'a'] == null)

        {

            return;

        }

        this.SearchOnBoard(this.root, board, i, j, result);     

    }

    

    private void SearchOnBoard(TrieNode node, char[][] board, int i, int j, List<string> result)

    {

        int index = board[i][j] - 'a';

        if (board[i][j] == '#' || node.Children[index] == null)

        {

            return;

        }

        node = node.Children[index];

        if (node.End > 0)

        {

            result.Add(node.Word);

            node.End--;

        }

        char temp = board[i][j];

        board[i][j] = '#'; // visited

        if (i > 0)

        {

            SearchOnBoard(node, board, i - 1, j, result);

        }

        if (i < board.Length - 1)

        {

            SearchOnBoard(node, board, i + 1, j, result);

        }

        if (j > 0)

        {

            SearchOnBoard(node, board, i, j - 1, result);

        }

        if (j < board[0].Length - 1)

        {

            SearchOnBoard(node, board, i, j + 1, result);

        }

        board[i][j] = temp;

    }

    private TrieNode root;

}

public class Solution 

{

    public IList<string> FindWords(char[][] board, string[] words) 

    {

        List<string> result = new List<string>();

        int rows = board?.Length ?? 0;

        if (rows == 0)

        {

            return result;

        }

        int cols = board[0].Length;

        int length = words.Length;

        if (length == 0)

        {

            return result;

        }

        Trie trie = new Trie();

        foreach(string word in words)

        {

            trie.Insert(word);

        }

        for (int i = 0; i < rows; ++i)

        {

            for (int j = 0; j < cols; ++j)

            {

                trie.SearchOnBoard(board, i, j, result);

            }

        }

        return result;

    }

}

Complexity: O( rows * cols * 3 ^ (length of the largest word in words)) 

[LeetCode] Search in Rotated Sorted Array II

Problem: There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

Example:

Input: nums = [1,0,1,1,1], target = 0
Output: true

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Approach: This question is similar to search an element is sorted rotated array but here the elements in the array might not be distinct. We will apply the same approach here with little modification to avoid duplicate values. You can look at the implementation to understand the extra step.

Implementation in C#:

    public bool Search(int[] nums, int target) 

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return false;

        }

        int start = 0, end = length - 1;

        while (start <= end && nums[start] == nums[end])

        {

            if (nums[start] == target)

            {

                return true;

            }

            ++start;

            --end;

        }  

        while (start <= end)

        {

            int mid = start + (end - start) / 2;            

            if (target == nums[mid]) 

            {

                return true;

            }     

            if (nums[start] <= nums[mid])

            {

                if (target >= nums[start] && target < nums[mid])

                {

                    end = mid - 1;

                }

                else

                {

                    start = mid + 1;

                }

            }

            else

            {

                if (target > nums[mid] && target <= nums[end])

                {

                    start = mid + 1;

                }

                else

                {

                    end = mid - 1;

                }

            }

        }        

        return false;

    }

Complexity: O(n)

[Google][LintCode] Add Bold Tag in String

Problem: Given a string s and a list of strings dict, you need to add a closed pair of bold tag and to wrap the substrings in s that exist in dict. If two such substrings overlap, you need to wrap them together by only one pair of closed bold tag. Also, if two substrings wrapped by bold tags are consecutive, you need to combine them.

Example:

Input: s = "abcxyz123", target = ["abc", "123"]
Output: "<b>abc</b>xyz<b>123</b>

Input: s = "aaabbcc", target = ["abc", "123"]
Output: "<b>aaabbc</b>c

Approach: Here we will take a marking boolean array which will tell us whether the current character should be mark bold or not. You can look at the implementation to understand the solution which very much straight forward.

Implementation in C#:

        public static string AddBoldTag(string s, string[] dict) 

{

            int length = s?.Length ?? 0;

            if (length == 0)

            {

                return null;

            }

            bool[] bold = new bool[length];

            int currEnd = 0;

            for (int i = 0; i < length; ++i)

            {

                foreach(string word in dict)

                {

                    if (StartsWith(s, i, word))

                    {

                        currEnd = Math.Max(currEnd, i + word.Length);

                    }

                }

                bold[i] = i < currEnd;

            }

            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < length; ++i)

            {

                if (bold[i] && (i == 0 || !bold[i - 1]))

                {

                    sb.Append("<b>");

                }

                sb.Append(s[i]);

                if (bold[i] && (i == length - 1 || !bold[i + 1]))

                {

                    sb.Append("</b>");

                }

            }

            return sb.ToString();

        }

private static bool StartsWith(string s, int index, string word)

        {

            for (int i = 0; i < word.Length; ++i)

            {

                if (index + i >= s.Length)

                {

                    return false;

                }

                if (s[index + i] != word[i])

                {

                    return false;

                }

            }

            return true;

        }

Complexity: O(n * w * lw) where n is the length of s, w is the number of strings in dict and lw is the length of the largest string in dict.

[LeetCode] 4Sum

Problem: Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Approach: We can sort this array and then can use two pointer approach to solve this problem.

Implementation in C#:

    public IList<IList<int>> FourSum(int[] nums, int target)

    {

        int length = nums?.Length ?? 0;

        var result = new List<IList<int>>();

        if (length <= 3)

        {

            return result;

        }

        Array.Sort(nums);

        for (int i = 0; i < length - 3; ++i)

        {

            if (i > 0 && nums[i] == nums[i - 1])

            {

                continue;

            }

            for (int j = i + 1; j < length - 2; ++j)

            {

                if (j > i + 1 && nums[j] == nums[j - 1])

                {

                    continue;

                }

                int k = j + 1;

                int l = length - 1;

                while (k < l)

                {

                    long currSum = (long)nums[i] +

                                   (long)nums[j] +

                                   (long)nums[k] +

                                   (long)nums[l];

                    if (currSum == target)

                    {

                        result.Add(new List<int>{nums[i],

                                                 nums[j],

                                                 nums[k++],

                                                 nums[l--]});

                        while (k < l && nums[k] == nums[k - 1])

                        {

                            ++k;

                        }

                        while (k < l && nums[l] == nums[l + 1])

                        {

                            --l;

                        }

                    }

                    else if (currSum < target)

                    {

                        ++k;

                    }

                    else

                    {

                        --l;

                    }

                }

            }

        }

        return result;

    }

Complexity: O(n^3)