126. Word Ladder II

Difficulty: Hard

Frequency: N/A

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
        m.clear();
        results.clear();
        path.clear();
        
        wordList.insert(beginWord);
        wordList.insert(endWord);
        
        unordered_set<string> cur_lev;
        cur_lev.insert(beginWord);
        unordered_set<string> next_lev;
        path.push_back(endWord);
        
        while (true) {
            // delete previous level words
            for (auto it = cur_lev.begin(); it != cur_lev.end(); it++) {
                wordList.erase(*it);
            }
            // find current level words
            for (auto it = cur_lev.begin(); it != cur_lev.end(); it++) {
                findDict(*it, wordList, next_lev);
            }
            if (next_lev.empty()) {
                return results;
            }
            // if find endWord
            if (next_lev.find(endWord) != wordList.end()) {
                output(beginWord, endWord);
                return results;
            }
            cur_lev.clear();
            cur_lev = next_lev;
            next_lev.clear();
        }
        return results;
    }
private:
    unordered_map<string, vector<string>> m;
    vector<vector<string>> results;
    vector<string> path;
    void findDict(string word, unordered_set<string>& wordList, unordered_set<string>& next_level) {
        int n = word.size();
        string s = word;
        for (int i = 0; i < n; i++) {
            s = word;
            for (int j = 0; j < 26; j++) {
                s[i] = 'a' + j;
                if (wordList.find(s) != wordList.end()) {
                    next_level.insert(s);
                    m[s].push_back(word);
                }
            }
        }
    }
    void output(string& start, string last) {
        if (last == start) {
            reverse(path.begin(), path.end());
            results.push_back(path);
            reverse(path.begin(), path.end());
        } else {
            for (int i = 0; i < m[last].size(); i++) {
                path.push_back(m[last][i]);
                output(start, m[last][i]);
                path.pop_back();
            }
        }
    }
};

Solution 2:

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


Submission errors:

 

Things to learn:

150. Evaluate Reverse Polish Notation

Difficulty: Medium

Frequency: N/A

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        if (tokens.empty()) return 0;
        int n = tokens.size(), result;
        stack<int> s;
        for (int i = 0; i < n; i++) {
            string tmp = tokens[i];
            if (tmp == "+" || tmp == "-" || tmp == "*" || tmp == "/") {
                int num2 = s.top();
                s.pop();
                int num1 = s.top();
                s.pop();
                if (tmp == "+") {
                    result = num1 + num2;
                } else if (tmp == "-") {
                    result = num1 - num2;
                } else if (tmp == "*") {
                    result = num1 * num2;
                } else {
                    result = num1 / num2;
                }
                s.push(result);
            } else {
                s.push(stoi(tmp));
            }
        }
        return s.top();
    }
};

Solution 2:

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


Submission errors:

 

Things to learn:

139. Word Break

Difficulty: Medium

Frequency: N/A

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".


Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        if (wordDict.empty()) return false;
        int n = s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (dp[j] == true) {
                    string word = s.substr(j, i - j);
                    if (wordDict.find(word) != wordDict.end()) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
        return dp[n];
    }
};

Solution 2:

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


Submission errors:

 

Things to learn:

266. (Locked)Palindrome Permutation

Difficulty: Easy

Frequency: N/A

Given a string, determine if a permutation of the string could form a palindrome.

For example,
"code" -> False, "aab" -> True, "carerac" -> True.

Hint:

  1. Consider the palindromes of odd vs even length. What difference do you notice?
  2. Count the frequency of each character.
  3. If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times?

Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    bool canPermutePalindrome(string s) {
        vector<int> count(256, 0);
        for (auto c : s) count[c]++;
        int oddCount = 0;
        for (auto i : count) {
            if (i % 2 != 0) oddCount++;
        }
        return oddCount <= 1;
    }
};

Solution 2:

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


Submission errors:

 

Things to learn:

228. Summary Ranges

Difficulty: Easy

Frequency: N/A

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].


Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> results;
        int n = nums.size();
        if (n == 0) return results;
        if (n == 1) {
            results.push_back(to_string(nums[0]));
            return results;
        }
        int pre = nums[0], start = pre, end = pre;
        for (int i = 1; i <= n; i++) {
            if (i == n || nums[i] != pre + 1) {
                if (end != start) {
                    string tmp = to_string(start) + "->" + to_string(end);
                    results.push_back(tmp);
                } else {
                    results.push_back(to_string(start));
                }
                pre = nums[i];
                start = end = pre;
            } else {
                pre = nums[i];
                end = pre;
            }
        }
        return results;
    }
};

Solution 2:

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


Submission errors:

 

Things to learn:

127. Word Ladder

Difficulty: Medium

Frequency: N/A

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
        wordList.insert(endWord);
        queue<string> toVisit;
        addNextWords(beginWord, wordList, toVisit);
        int dist = 2;
        while (!toVisit.empty()) {
            int n = toVisit.size();
            for (int i = 0; i < n; i++) {
                string word = toVisit.front();
                toVisit.pop();
                if (word == endWord) return dist;
                addNextWords(word, wordList, toVisit);
            }
            dist++;
        }
    }
private:
    void addNextWords(string word, unordered_set<string>& wordList, queue<string>& toVisit) {
        wordList.erase(word);
        for (int i = 0; i < (int)word.size(); i++) {
            char c = word[i];
            for (int j = 0; j < 26; j++) {
                word[i] = 'a' + j;
                if (wordList.find(word) != wordList.end()) {
                    toVisit.push(word);
                    wordList.erase(word);
                }
            }
            word[i] = c;
        }
    }
};

Solution 2:

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


Submission errors:

 

Things to learn:

071. Simplify Path

Difficulty: Medium

Frequency: N/A

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.

Corner Cases:

  • Did you consider the case where path = "/../"?
    In this case, you should return "/".
  • Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
    In this case, you should ignore redundant slashes and return "/home/foo".

Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    string simplifyPath(string path) {
        vector<string> paths;
        string tmp;
        stringstream ss(path);
        while (getline(ss, tmp, '/')) {
            if (tmp == "" || tmp == ".") continue;
            if (tmp == ".." && !paths.empty()) paths.pop_back();
            else if (tmp != "..") paths.push_back(tmp);
        }
        string result;
        for (string s : paths) result += "/" + s;
        return result.empty() ? "/" : result;
    }
};

Solution 2:

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


Submission errors:

 

Things to learn:

068. Text Justification

Difficulty: Hard

Frequency: N/A

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly Lcharacters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> results;
        int n, length;
        for (int i = 0; i < words.size(); i += n) {
            for (n = 0, length = 0; i + n < words.size() && length + words[i + n].size() <= maxWidth - n; n++) {
                length += words[i + n].size();
            }
            string result = words[i];
            for (int j = 0; j < n - 1; j++) {
                if (i + n == words.size()) result += " ";
                else result += string((maxWidth - length) / (n - 1) + (j < (maxWidth - length) % (n - 1)), ' ');
                result += words[i + j + 1];
            }
            result += string(maxWidth - result.size(), ' ');
            results.push_back(result);
        }
        return results;
    }
};

Solution 2:

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


Submission errors:

 

Things to learn:

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:

132. Palindrome Partitioning II

Difficulty: Hard

Frequency: N/A

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

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.


Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<int> cuts(n + 1, 0);
        for (int i = 0; i <= n; i++) cuts[i] = i - 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; i - j >= 0 && i + j < n && s[i - j] == s[i + j]; j++) {
                cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i - j] + 1);
            }
            for (int j = 1; i - j + 1 >= 0 && i + j < n && s[i - j + 1] == s[i + j]; j++) {
                cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i - j + 1] + 1);
            }
        }
        return cuts[n];
    }
};

Solution 2:

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


Submission errors:

 

Things to learn: