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:

Advertisements

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: