Mind palace

17. Letter Combinations of a Phone Number

Posted on 2020-05-31 Edited on 2021-02-04 In LeetCode Disqus:
Symbols count in article: 3.2k Reading time ≈ 3 mins.

iterative O(3ⁿ) time

m = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

import itertools as it

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        chars = [m[int(d)] for d in digits]
        return [''.join(p) for p in it.product(*chars)]

m = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        return reduce(lambda res, d : [s + c for s in res for c in m[d]], map(int, digits), [''])

用这个

m = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        res = ['']
        for d in map(int, digits):
            res = [s + c for s in res for c in m[d]]
        return res

m = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        res = ['']
        for d in digits:
            t = []
            for s in res:
                for c in m[int(d)]:
                    t.append(s + c)
            res = t
        return res

dfs

m = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        if len(digits) == 1: return list(m[int(digits)])
        res = self.letterCombinations(digits[: -1]) # 前边的结果已经出来了，只需要计算当前的最后一个字符即可
        return [s + c for s in res for c in m[int(digits[-1])]]

iterative

string m[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

class Solution {
public:
    /*
     * @param digits: A digital string
     * @return: all posible letter combinations
     */
    vector<string> letterCombinations(string &digits) {
        // write your code here
        vector<string> res;
        if (digits.empty()) return res;
        res.push_back(""); // 一定要放一个空串！！！
        for (char d : digits) {
            vector<string> t;
            for (const auto &s : res) {
                for (char c : m[d - '0']) {
                    t.push_back(s + c);
                }
            }
            res.swap(t);
        }
        return res;
    }
};

recursive O(3ⁿ) time

string m[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

class Solution {
public:
    /*
     * @param digits: A digital string
     * @return: all posible letter combinations
     */
    vector<string> letterCombinations(string &digits) {
        // write your code here
        vector<string> res;
        if (digits.empty()) return res;
        dfs("", digits, res);
        return res;
    }

    void dfs(const string &s, const string &d, vector<string> &res) {
        if (s.length() == d.length()) {
            res.push_back(s);
            return;
        }
        for (char c : m[d[s.length()] - '0']) {
            dfs(s + c, d, res);
        }
    }
};

16. 3Sum Closest

Posted on 2020-05-31 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

two pointers O(n²)

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n, d, res = len(nums), float('inf'), 0
        for i in range(n):
            if i > 0 and nums[i - 1] == nums[i]: continue
            l, r, t = i + 1, n - 1, target - nums[i]
            while l < r:
                s = nums[l] + nums[r]
                if abs(s - t) < d:
                    d, res = abs(s - t), s + nums[i]
                if s < t:
                    l += 1
                    while l < r and nums[l - 1] == nums[l]:
                        l += 1
                elif s > t:
                    r -= 1
                    while l < r and nums[r] == nums[r + 1]:
                        r -= 1
                else:
                    return res
        return res

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int i = 0;
        int diff = INT_MAX;
        int res = 0;
        while (i < n) {
            int l = i + 1, r = n - 1;
            int t = target - nums[i];
            while (l < r) {
                int sum = nums[l] + nums[r];
                if (abs(sum - t) < diff) {
                    diff = abs(sum - t);
                    res = nums[i] + sum;
                }
                if (sum == t) {
                    return target;
                } else if (sum < t) {
                    do { ++l; } while (l < r && nums[l] == nums[l - 1]);
                } else {
                    do { --r; } while (l < r && nums[r] == nums[r + 1]);
                }
            }
            do { ++i; } while (i < n && nums[i] == nums[i - 1]);
        }
        return res;
    }
};

15. 3Sum

Posted on 2020-05-31 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

two pointers O(n²)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        res = []
        for i in range(n):
            if i > 0 and nums[i - 1] == nums[i]: continue
            t = -nums[i]
            l, r = i + 1, n - 1
            while l < r:
                s = nums[l] + nums[r]
                if s == t:
                    res.append([nums[i], nums[l], nums[r]])
                    l += 1
                    while l < r and nums[l - 1] == nums[l]: l += 1
                    r -= 1
                    while l < r and nums[r] == nums[r + 1]: r -= 1
                elif s < t:
                    l += 1
                    while l < r and nums[l - 1] == nums[l]: l += 1
                else:
                    r -= 1
                    while l < r and nums[r] == nums[r + 1]: r -= 1
        return res

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            long t = -(long)nums[i];
            int l = i + 1, r = n - 1;
            while (l < r) {
                long s = (long)nums[l] + nums[r];
                if (s == t) {
                    res.push_back({nums[i], nums[l], nums[r]});
                    do { ++l; } while (l < r && nums[l] == nums[l - 1]);
                    do { --r; } while (l < r && nums[r] == nums[r + 1]);
                } else if (s < t) {
                    do { ++l; } while (l < r && nums[l] == nums[l - 1]);
                } else {
                    do { --r; } while (l < r && nums[r] == nums[r + 1]);
                }
            }
        }
        return res;
    }
};

14. Longest Common Prefix

Posted on 2020-05-31 Edited on 2021-02-04 In LeetCode Disqus:
Symbols count in article: 3.5k Reading time ≈ 3 mins.

O(mn) time
vertical scan

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        res = ''
        for x in zip(*strs):
            if len(set(x)) != 1: break
            res += x[0]
        return res

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        res = ''
        for x in zip(*strs):
            if all(c == x[0] for c in x):
                res += x[0]
            else:
                break
        return res

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        for (int i = 0; i < size(strs[0]); ++i) {
            for (int j = 1; j < size(strs); ++j) {
                if (i >= size(strs[j]) || strs[j][i] != strs[j - 1][i]) return strs[0].substr(0, i);
            }
        }
        return strs[0];
    }
};

horizontal scan
循环依次检查即可

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ''
        res = strs[0]
        for i in range(1, len(strs)):
            res = self.resolve(res, strs[i])
            if not res:
                break
        return res

    def resolve(self, A, B):
        res = ''
        for i in range(min(len(A), len(B))):
            if A[i] != B[i]: break
            res += A[i]
        return res

trie

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Solution:

    def __init__(self):
        self.root = TrieNode()

    def add(self, s):
        p = self.root
        for c in s:
            if c not in p.children:
                p.children[c] = TrieNode()
            p = p.children[c]
        p.is_end = True

    def search(self):
        '''first approach'''
        res = ''
        p = self.root
        while len(p.children) == 1:
            k, v = list(p.children.items())[0]
            res += k
            p = v
            if p.is_end: break
        return res

    def search1(self):
        '''second approach'''
        res = ''
        p = self.root
        while len(p.children) == 1:
            res += list(p.children.keys())[0]
            p = list(p.children.values())[0]
            if p.is_end: break
        return res

    def search2(self):
        '''third approach'''
        res = ''
        p = self.root
        while len(p.children) == 1:
            res += next(iter(p.children))
            p = next(iter(p.children.values()))
            if p.is_end: break
        return res

    def longestCommonPrefix(self, strs: List[str]) -> str:
        for s in strs:
            if not s: return ''
            self.add(s)
        return self.search()

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        int n = strs.size();
        string res = strs[0];
        for (int i = 1; i < n && !res.empty(); ++i) {
            res = helper(res, strs[i]);
        }
        return res;
    }

    string helper(const string &p, const string &s) {
        int n = min(p.length(), s.length());
        string res;
        for (int i = 0; i < n && p[i] == s[i]; ++i) {
            res += p[i];
        }
        return res;
    }
};

trie

class Solution {
public:
    struct TrieNode {
        unordered_map<char, TrieNode*> children;
        bool isEnd = false;
    };
    TrieNode *root = nullptr;
    string longestCommonPrefix(vector<string>& strs) {
        root = new TrieNode;
        for (const auto &s : strs) {
            add(s);
        }
        string res;
        auto p = root;
        while (p && !p->isEnd && p->children.size() == 1) {
            auto &&[c, n] = *begin(p->children);
            res += c;
            p = n;
        }
        return res;
    }
    void add(const string &s) {
        auto p = root;
        for (char c : s) {
            if (!p->children.count(c)) {
                p->children[c] = new TrieNode;
            }
            p = p->children[c];
        }
        p->isEnd = true;
    }
};

O(mnlogn) time

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        sort(begin(strs), end(strs));
        int n = min(strs.front().length(), strs.back().length());
        string res;
        for (int i = 0; i < n && strs.front()[i] == strs.back()[i]; ++i) {
            res += strs.front()[i];
        }
        return res;
    }
};

13. Roman to Integer

Posted on 2020-05-31 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 1.7k Reading time ≈ 2 mins.

O(n)
一般罗马数字都是从大到小排列，如果发现当前数字小于下一个，如IV，则减去当前数字，即-1 + 5 = 4

d = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}

class Solution:
    def romanToInt(self, s: str) -> int:
        res = 0
        for i in range(len(s)):
            if i > 0 and d[s[i - 1]] < d[s[i]]:
                res -= d[s[i - 1]] * 2
            res += d[s[i]]
        return res

d = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}

class Solution:
    def romanToInt(self, s: str) -> int:
        res, n = 0, len(s)
        for i in range(n):
            if i + 1 < n and d[s[i]] < d[s[i + 1]]:
                res -= d[s[i]]
            else:
                res += d[s[i]]
        return res

unordered_map<char, int> m = {
    {'I', 1},
    {'V', 5},
    {'X', 10},
    {'L', 50},
    {'C', 100},
    {'D', 500},
    {'M', 1000}
};
class Solution {
public:
    int romanToInt(string s) {
        int res = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (i + 1 < n && m[s[i]] < m[s[i + 1]]) {
                res -= m[s[i]];
            } else {
                res += m[s[i]];
            }
        }
        return res;
    }
};

unordered_map<char, int> m = {
    {'I', 1},
    {'V', 5},
    {'X', 10},
    {'L', 50},
    {'C', 100},
    {'D', 500},
    {'M', 1000}
};
class Solution {
public:
    int romanToInt(string s) {
        int res = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (i > 0 && m[s[i]] > m[s[i - 1]]) {
                res -= m[s[i - 1]] * 2;
            }
            res += m[s[i]];
        }
        return res;
    }
};

12. Integer to Roman

Posted on 2020-05-30 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 1.4k Reading time ≈ 1 mins.

O(1)

M = ['', 'M', 'MM', 'MMM']
C = ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM']
X = ['', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC']
I = ['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX']

class Solution:
    def intToRoman(self, num: int) -> str:
        return M[num // 1000] + C[num % 1000 // 100] + X[num % 100 // 10] + I[num % 10]

string M[] = {"", "M", "MM", "MMM"};
string C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
string X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
string I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

class Solution {
public:
    string intToRoman(int num) {
        return M[num / 1000] + C[num % 1000 / 100] + X[num % 100 / 10] + I[num % 10];
    }
};

11. Container With Most Water

Posted on 2020-05-30 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 684 Reading time ≈ 1 mins.

two pointers O(n)
这道题和maximum square不一样
思路和trapping most water类似，都是维护左右两个指针从外往里找短板，当前最大面积更新后，短板必须要更新成更长的板

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r, res = 0, len(height) - 1, 0
        while l < r:
            mn = min(height[l], height[r])
            res = max(res, mn * (r - l))
            while l < r and height[l] <= mn:
                l += 1
            while l < r and height[r] <= mn:
                r -= 1
        return res

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int res = 0;
        int l = 0, r = n - 1;
        while (l < r) {
            int mn = min(height[l], height[r]);
            res = max(res, mn * (r - l));
            while (l < r && height[l] <= mn) {
                ++l;
            }
            while (l < r && height[r] <= mn) {
                --r;
            }
        }
        return res;
    }
};

10. Regular Expression Matching

Posted on 2020-05-30 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 2.9k Reading time ≈ 3 mins.

O(mn) time O(m+n) space
只有p[n - 1]为*那种情况才有可能需要向两个方向递归（其他单向递归的时间复杂度不会超过这个），一个方向m层，另外一个方向n层，对于每一层都有可能向另外一个方向递归，所以时间复杂度是O(mn)

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        f = [[False] * (n + 1) for i in range(m + 1)]
        f[0][0] = True
        for i in range(1, n + 1):
            f[0][i] = (p[i - 1] == '*') and f[0][i - 2]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    f[i][j] = f[i][j - 2] or (f[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.'))
                else:
                    f[i][j] = f[i - 1][j - 1] and (s[i - 1] == p[j - 1] or p[j - 1] == '.')
        return f[m][n]

class Solution {
public:
    bool isMatch(string s, string p) {
        return isMatch(s, s.length(), p, p.length()); // 从后往前分析
    }

    bool isMatch(const string &s, int m, const string &p, int n) {
        if (m == 0 && n == 0) return true; // 两个空串肯定匹配
        if (m != 0 && n == 0) return false; // 如果s不空p空肯定不匹配
        if (m == 0 && n != 0) return p[n - 1] == '*' && isMatch(s, m, p, n - 2); // 如果s空p不空，则只有可能p是类似a*a*a*这样的
        if (p[n - 1] == '*') return (s[m - 1] == p[n - 2] || p[n - 2] == '.') && isMatch(s, m - 1, p, n) || isMatch(s, m, p, n - 2); // 如果p以*结尾，则(1)要不s[m - 1]跟p[n - 2]匹配（包括p[n - 2]是.的情况）并且s[0:m-1)和p[0:n)匹配（这里之所以是p[0:n)不是p[0:n-2)是因为s[0:m-1)未必能跟p[0:n-2)匹配但是有可能跟p[0:n)匹配，比如s是xxxzz，p是xxxz*，xxx跟xxxz不匹配但是xxxz*可以跟xxxz匹配，所以这里要用整个p去尝试匹配s[0:m-1)）(2)要不s[0:m)跟p[0:n - 2)匹配
        return (s[m - 1] == p[n - 1] || p[n - 1] == '.') && isMatch(s, m - 1, p, n - 1); // 如果p不以*结尾，则s[m - 1]跟p[n - 1]匹配（或者p[n - 1]为.）并且s[0:m-1)跟p[0:n-1)匹配
    }
};

dp O(mn) time O(mn) space
这道题中”a*”的意思是若干个a

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        vector<vector<bool>> f(m + 1, vector<bool>(n + 1));
        f[0][0] = true;
        for (int j = 1; j <= n; ++j) {
            f[0][j] = (p[j - 1] == '*') && f[0][j - 2];
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    f[i][j] = f[i][j - 2] || f[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.');
                } else {
                    f[i][j] = f[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
                }
            }
        }
        return f[m][n];
    }
};

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.length(), m = p.length();
        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1));
        dp[0][0] = true; // 两个空串肯定匹配
        for (int j = 1; j <= m; ++j) {
            if (p[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2]; // 前一个字符p[j - 2]相当于循环节，所以要继承前前个结果，即循环节之前的匹配结果
            }
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1]; // 如果字符相同或者正则字符是.直接继承之前两个串的匹配结果
                } else if (p[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.')); // 因为p[j - 2]是循环节，所以要检查前前个结果dp[i][j - 2]，即循环节之前的匹配结果；另外，如果之前的字符串s[0:i-2]已经和p[0:j-1]匹配，即dp[i - 1][j]为true，那么就要看当前字符是否和正则字符（循环节p[j-2]）匹配；这里一定要考虑清楚逻辑！！用OR是对的，ifelse可能出问题
                }
            }
        }
        return dp[n][m];
    }
};

9. Palindrome Number

Posted on 2020-05-30 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 388 Reading time ≈ 1 mins.

O(1) time O(1) space

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x == 0: return True
        if x < 0 or x % 10 == 0: return False
        y = 0
        while x > y:
            y = y * 10 + x % 10
            x //= 10
        return x == y or x == y // 10

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0 || x != 0 && x % 10 == 0) return false; // 负数和结尾是0的正数都不合法
        int y = 0;
        while (x > y) {
            y = y * 10 + x % 10;
            x /= 10;
        }
        return x == y || x == y / 10;
    }
};

8. String to Integer (atoi)

Posted on 2020-05-30 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 1.9k Reading time ≈ 2 mins.

class Solution:
    def myAtoi(self, str: str) -> int:
        res, MAX, MIN = 0, (1 << 31) - 1, -(1 << 31)
        str = str.lstrip()
        if not str: return 0
        sign, i = 1, 0
        if str[0] in '+-':
            sign, i = 44 - ord(str[0]), 1
        for i in range(i, len(str)):
            if res > MAX or not str[i].isdigit(): break
            res = res * 10 + int(str[i])
        res *= sign
        if res < MIN: return MIN
        return res if res <= MAX else MAX

class Solution {
public:
    int myAtoi(string str) {
        if (str.empty()) return 0;
        int n = str.length();
        int b = 0;
        while (str[b] == ' ') {
            ++b;
        }
        int sign = 1;
        if (str[b] == '+' || str[b] == '-') {
            sign = 44 - str[b];
            ++b;
        }
        long res = 0;
        for (int i = b; i < n && isdigit(str[i]) && res <= INT_MAX; ++i) {
            res = res * 10 + str[i] - '0';
        }
        res *= sign;
        if (res < INT_MIN) return INT_MIN;
        return res <= INT_MAX ? res : INT_MAX;
    }
};

class Solution {
public:
    int myAtoi(string str) {
        long res = 0;
        int n = str.length();
        int b = 0;
				// 去掉开始的空格
        while (str[b] == ' ') {
            ++b;
        }
        int sign = 1;
        if (str[b] == '-' || str[b] == '+') { // 判断符号，注意b++
            if (str[b++] == '-') sign = -1;
        }
        for (int i = b; i < n && isdigit(str[i]) && res <= INT_MAX; ++i) { // 三个条件：不能越界、必须是数字、值不能超过INT_MAX（INT_MIN可行）
            res = res * 10 + str[i] - '0';
        }
        res *= sign;
        if (res > INT_MAX) return INT_MAX;
        if (res < INT_MIN) return INT_MIN;
        return res;
    }
};

class Solution {
public:
    int myAtoi(string str) {
        if (str.empty()) return 0;
        long res = 0;
        int b = 0;
        int n = str.length();
        while (b < n && str[b] == ' ') {
            ++b;
        }
        bool ispos = true;
        if (str[b] == '-') {
            ispos = false;
            ++b;
        } else if (str[b] == '+') {
            ++b;
        }
        for (int i = b; i < n && res <= INT_MAX && '0' <= str[i] && str[i] <= '9'; ++i) {
            res = res * 10 + str[i] - '0';
        }
        return ispos ? min((long)INT_MAX, res) : max((long)INT_MIN, -res);
    }
};