140. Word Break II

Difficulty: Hard

Frequency: N/A

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].


Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
private:
    unordered_map<string, vector<string>> m;
    vector<string> combine(string word, vector<string> prev) {
        for (int i = 0; i < prev.size(); i++) prev[i] += " " + word;
        return prev;
    }
public:
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        if (m.count(s)) return m[s];
        vector<string> results;
        if (wordDict.count(s)) results.push_back(s);
        for (int i = 1; i < s.size(); i++) {
            string word = s.substr(i);
            if (wordDict.count(word)) {
                string rem = s.substr(0, i);
                vector<string> prev = combine(word, wordBreak(rem, wordDict));
                results.insert(results.end(), prev.begin(), prev.end());
            }
        }
        m[s] = results;
        return results;
    }
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:


Submission errors:

 

Things to learn:

Advertisements

254. (Locked)Factor Combinations

Difficulty:  Medium

Frequency: N/A

Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note:

  1. Each combination’s factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].
  2. You may assume that n is always positive.
  3. Factors should be greater than 1 and less than n.

 

Examples:
input: 1
output:

[]

input: 37
output:

[]

input: 12
output:

[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

input: 32
output:

[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
        vector<vector<int> > getFactors(int n) {
                vector<vector<int> > results;
                vector<int> tmp;
                helper(n, tmp, results);
                return results;
        }

        void helper(int n, vector<int> tmp, vector<vector<int> > &results) {
                int i = tmp.empty() ? 2 : tmp.back();
                for (; i <= n / i; i++) {
                        if (n % i == 0) {
                                tmp.push_back(i);
                                tmp.push_back(n / i);
                                results.push_back(tmp);
                                tmp.pop_back();
                                helper(n / i, tmp, results);
                                tmp.pop_back();
                        }
                }
        }
};



Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

079. Word Search

Difficulty: Medium

Frequency: N/A

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) return false;
        vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
        for (int row = 0; row < board.size(); row++) {
            for (int column = 0; column < board[row].size(); column++) {
                    if (findWord(word, 0, board, visited, row, column)) return true;
            }
        }
        return false;
    }
    bool findWord(string &word, int idx, vector<vector<char>> &board, vector<vector<bool>> &visited, int row, int column) {
        if (idx == word.size()) return true;
        if (row < 0 || row >= board.size() || column < 0 || column >= board[0].size()) return false;
        if (!visited[row][column] && board[row][column] == word[idx]) {
            visited[row][column] = true;
            if (findWord(word, idx + 1, board, visited, row - 1, column)) return true;
            if (findWord(word, idx + 1, board, visited, row + 1, column)) return true;
            if (findWord(word, idx + 1, board, visited, row, column - 1)) return true;
            if (findWord(word, idx + 1, board, visited, row, column + 1)) return true;
            visited[row][column] = false;
        }
        return false;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
1. If TLE, try to use reference as parameter.

093. Restore IP Addresses

Difficulty: Medium

Frequency: N/A

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> results;
        vector<string> tmp;
        helper(0, 0, s, tmp, results);
        return results;
    }
    
    void helper(int part_num, int start_idx, string s, vector<string> tmp, vector<string> &results) {
        if (part_num == 4 && start_idx == s.size()) {
            string result;
            for (int i = 0; i < tmp.size(); i++) result = result + tmp[i] + ".";
            results.push_back(result.substr(0, result.size() - 1));
            return;
        }
        if (((s.size() - start_idx) > (4 - part_num) * 3) || ((s.size() - start_idx) < (4 - part_num))) return;
        for (int idx = start_idx; idx < start_idx + 3; idx++) {
            if (valid(s.substr(start_idx, idx - start_idx + 1))) {
                tmp.push_back(s.substr(start_idx, idx - start_idx + 1));
                helper(part_num + 1, idx + 1, s, tmp, results);
                tmp.pop_back();
            }
        }

    }
    
    bool valid(string s) {
        if (s.size() > 3) return false;
        else if (s.size() > 1 && s[0] == '0') return false;
        else {
            int num = 0;
            for (int i = 0; i < s.size(); i++) {
                num = num + (s[i] - '0') * pow(10, s.size() - i - 1);
            }
            if (num > 255) return false;
        }
        return true;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

037. Sudoku Solver

Difficulty: Hard

Frequency: N/A

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle…

…and its solution numbers marked in red.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        helper(board, 0);
    }
    bool helper(vector<vector<char>> &board, int idx) {
        if (idx == 81) return true;
        int row = idx / 9;
        int column = idx % 9;
        if (board[row][column] != '.') {
            return helper(board, idx + 1);
        } else {
            for (char c = '1'; c <= '9'; c++) {
                if (isValid(row, column, c, board)) {
                    board[row][column] = c;
                    if (helper(board, idx + 1)) return true;
                    else board[row][column] = '.';
                }
            }
            return false;
        }
    }
    bool isValid(int row, int column, char num, vector<vector<char>> &board) {
        int size = board.size();
        for (int i = 0; i < size; i++) {
            if (board[row][i] == num) return false;
        }
        for (int i = 0; i < size; i++) {
            if (board[i][column] == num) return false;
        }
        for (int i = row / 3 * 3; i < row / 3 * 3 + 3; i++) {
            for (int j = column / 3 * 3; j < column / 3 * 3 + 3; j++) {
                if (board[i][j] == num) return false;
            }
        }
        return true;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
1. Need to handle backing out the backtracking early.

060. Permutation Sequence

Difficulty: Medium

Frequency: N/A

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    string getPermutation(int n, int k) {
        string result;
        vector<int> fac(n, 1);
        for (int i = 1; i < n; i++) fac[i] = fac[i - 1] * i;
        vector<int> nums;
        for (int i = 0; i < n; i++) nums.push_back(i + 1);
        k--;
        for (int i = n; i > 0; i--) {
            int idx = k / fac[i - 1];
            k = k % fac[i - 1];
            result = result + to_string(nums[idx]);
            nums.erase(nums.begin() + idx);
        }
        return result;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

131. Palindrome Partitioning

Difficulty: Medium

Frequency: N/A

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> results;
        vector<string> tmp;
        helper(s, 0, tmp, results);
        return results;
    }
    void helper(string s, int idx, vector<string> tmp, vector<vector<string>> &results) {
        if (idx == s.size()) {
            results.push_back(tmp);
            return;
        }
        for (int i = idx; i < s.size(); i++) {
            if (isPalindrome(s.substr(idx, i - idx + 1))) {
                tmp.push_back(s.substr(idx, i - idx + 1));
                helper(s, i + 1, tmp, results);
                tmp.pop_back();
            }
        }
    }
    bool isPalindrome(string s) {
        if (s.size() == 1) return true;
        for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
            if (s[i] != s[j]) return false;
        }
        return true;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: