Palindrome

5. Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

这一题是很多题目的基础, 最长回文串

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() < 2)
            return s;
        int len = s.size(), max_left = 0, max_len = 1, left, right;
        for (int start = 0; start < len && len - start > max_len / 2;) {
            left = right = start;
            while (right < len - 1 && s[right + 1] == s[right])
                ++right;
            start = right + 1;
            while (right < len - 1 && left > 0 && s[right + 1] == s[left - 1]) {
                ++right;
                --left;
            }
            if (max_len < right - left + 1) {
                max_left = left;
                max_len = right - left + 1;
            }
        }
        return s.substr(max_left, max_len);
    }
};

214. Shortest Palindrome

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation. For example: Given "aacecaaa", return "aaacecaaa". Given "abcd", return "dcbabcd".

暴力解:

class Solution {
public:
    string shortestPalindrome(string s) {
        int len = s.size();
        if (len <= 1) return s;
        string reversed(s);
        reverse(reversed.begin(), reversed.end());

        for (int i = 0; i < s.size(); ++i) {
            if (reversed.substr(i) == s.substr(0, len - i)) {
                return reversed.substr(0, i) + s;
            }
        }

        return s;
    }
};

336. Palindrome Pairs

Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

Example 1:
Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]

Example 2:
Given words = ["abcd", "dcba", "lls", "s", "sssll"]
Return [[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]
class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        unordered_map<string, int> word2idx;
        vector<vector<int>> res;
        for (size_t i = 0; i < words.size(); ++i) {
            word2idx[words[i]] = i;
        }

        for (int i = 0; i < words.size(); ++i) {
            for (size_t j = 0; j <= words[i].size(); ++j) {
                auto left = words[i].substr(0,j);
                auto right = words[i].substr(j);
                auto rl = left;
                auto rr = right;
                reverse(rl.begin(), rl.end());
                reverse(rr.begin(), rr.end());
                if (word2idx.find(rl) != word2idx.end() && isPalindrome(right) && word2idx[rl] != i) {
                    res.push_back({i, word2idx[rl]});
                }
                if (j > 0 && word2idx.find(rr) != word2idx.end() && isPalindrome(left) && word2idx[rr] != i) {
                    res.push_back({word2idx[rr], i});
                }


            }
        }
        return res;
    }


    bool isPalindrome(const string& s) {
        int len = s.size();
        if (len <= 1) return true;
        int i = 0;
        int j = len - 1;
        while (i < j) {
            if(s[i++] != s[j--]) return false;
        }
        return true;
    }
};

7. Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321 Example2: x = -123, return -321

class Solution {
public:
    int reverse(int x) {
        if (x == 0) return 0;
        int sign = x > 0;
        long long data = labs(x);
        long long reversed = 0;
        while (data) {
            reversed = reversed * 10 + (data % 10);
            data /= 10;
        }
        if (!sign) reversed *= -1;
        if (reversed > INT_MAX || reversed < INT_MIN) return 0;
        return static_cast<int>(reversed);
    }
};

9. Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

class Solution {
public:
    bool isPalindrome(int x) {
        if (x<0) return false;
        long long reversed = 0;
        long long data = x;
        while (x) {
            reversed = reversed*10 + (x % 10);
            x /= 10;
        }
        return reversed == data;
    }
};

234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up: Could you do it in O(n) time and O(1) space?

基本想法是找到中点,然后翻转后半部分

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return true;
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* pre = nullptr;
        while (fast && fast->next) {
            fast = fast->next->next;
            pre = slow;
            slow = slow->next;
        }
        ListNode* l2 = slow;
        pre->next = nullptr;
        l2 = reverseList(l2);

        while (head && l2) {
            if (head->val != l2->val) return false;
            head = head->next;
            l2 = l2->next;
        }

        return true;

    }

    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;

        ListNode* cur = head;
        ListNode* next = head->next;
        cur->next = nullptr;
        ListNode* newHead = reverseList(next);
        next->next = cur;
        return newHead;
    }
};

Recursive solution.
An easy understanding would be using a stack instead, since both of them using O(N) space, explicitly or implicitly.

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* cur = head;
        return isEqual(head, &cur);
    }

    bool isEqual(ListNode* head, ListNode** cur) {
        if (!head) return true;
        bool isPal = isEqual(head->next, cur) && ((*cur)->val == head->val);
        (*cur) = (*cur)->next;
        return isPal;
    }
};

131. Palindrome Partitioning

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"] ]

class Solution {
public:
    vector<vector<string>> partition(string s) {
        unordered_map<string, vector<vector<string>>> memo;
        vector<vector<string>> res;

        std::function<vector<vector<string>>(string& )> dfs = [&](string& str) {
            if (memo.find(str) != memo.end()) return memo[str];
            if (isPalindrome(str, 0, str.size() - 1)) {
                res.push_back({str});
            }

            for (int i = 1; i < str.size(); ++i) {
                if (isPalindrome(str, 0, i)) {
                    auto left = str.substr(0, i);
                    auto right = str.substr(i);
                    auto ret = dfs(right);
                    for (auto lst : ret) {
                        res.push_back({left});
                        for (auto str : lst) res.back().push_back(str);
                    }
                }
            }
            memo[str] = res;
            return res;
        };

        return dfs(s);
    }

    bool isPalindrome(const string& s, int i, int j) {
        if (j - i <= 1) return true;
        while (i < j) {
            if (s[i++] != s[j--]) return false;
        }
        return true;
    }
};

132. Palindrome Partitioning II

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.

class Solution {
public:
    int minCut(string s) {
        size_t len = s.size();
        vector<int> dp(len+1);
        for (size_t i = 0; i < len + 1; ++i) dp[i] = i - 1;

        for (int i = 0; i < len; ++i) {
            for (int j = 0; j <= i && i + j < len && s[i-j] == s[i+j]; ++j)
                dp[i+j+1] = min(dp[i+j+1], 1 + dp[i-j]);
            for (int j = 1; i -j + 1 >= 0 && j + i < len && s[i-j+1] == s[i+j]; ++j)
                dp[i+j+1] = min(dp[i+j+1], 1 + dp[i-j+1]);
        }

        return dp[len];
    }
};

214. Shortest Palindrome

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa". Given "abcd", return "dcbabcd".

brute force solution:

class Solution {
public:
    string shortestPalindrome(string s) {
        int len = s.size();
        if (len <= 1) return s;
        string reversed(s);
        reverse(reversed.begin(), reversed.end());

        for (int i = 0; i < s.size(); ++i) {
            if (reversed.substr(i) == s.substr(0, len - i)) {
                return reversed.substr(0, i) + s;
            }
        }

        return s;
    }
};

246 Strobogrammatic Number

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write a function to determine if a number is strobogrammatic. The number is represented as a string. For example, the numbers "69", "88", and "818" are all strobogrammatic.

class Solution {
public:
    bool isStrobogrammatic(string nums) {
        if (nums.size() == 0) return true;
        unordered_map<char, char> dict{{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
        int i = 0;
        int j = nums.size() - 1;
        while (i <= j) {
            if (dict.find(nums[i]) == dict.end() || dict.find(nums[j]) == dict.end()) return false;
            if (nums[i] != dict[nums[j]] || nums[j] != dict[nums[i]]) return false;
            ++i;
            --j;
        }
        return true;
    }
};

247 Strobogrammatic Number II

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Find all strobogrammatic numbers that are of length = n.

For example, Given n = 2, return ["11","69","88","96"].

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        return findStrobogrammatic(n, n);
    }

    vector<string> findStrobogrammatic(int n, int m) {
        if (n <= 0) return {""};
        if (n == 1) return {"0", "1", "8"};
        auto prev = findStrobogrammatic(n - 2, m);
        vector<string> res;
        for (auto str : prev) {
            if (n != m)
                res.push_back("0" + str + "0");
            res.push_back("1" + str + "1");
            res.push_back("6" + str + "9");
            res.push_back("8" + str + "8");
            res.push_back("9" + str + "6");
        }
        return res;
    }
};
class Solution_v2 {
public:
    vector<string> findStrobogrammatic(int n) {
        vector<vector<char>> pairs = {{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
        vector<string> res;
        string slu(n, '0');
        function<void(string&, int, int)> dfs =
            [&](string& str, int left, int right) {
            if (left > right) {
                res.push_back(str);
                // cout << str << endl;
                return;
            }

            for (auto p : pairs) {
                str[left] = p[0];
                str[right] = p[1];
                if (str.length() != 1 && str[0] == '0') continue;
                if (left < right  || (left == right && p[0] == p[1]))
                    dfs(str, left+1, right-1);
            }
        };

        dfs(slu, 0, n-1);
        return res;
    }
};

248 Strobogrammatic Number III

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high. For example,

Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.

Note: Because the range might be a large number, the low and high numbers are represented as string.

class Solution {
public:
    int strobogrammaticInRange(string low, string high) {
        int count = 0;
        vector<vector<int>> pairs = {{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
        for (auto len = low.size(); len <= high.size(); ++len) {
            string str(len, '0');
            dfs(low, high, str, 0, len - 1, count, pairs);
        }
        return count;
    }

    void dfs(string& low, string& high, string& str, int left, int right, int& count, vector<vector<int>>& pairs) {
        if (left > right) {
            if ((str.length() == low.length() && str < low) ||
                (str.length() == high.length() && str > high)) return;
            cout << str << endl;
            count++;
            return;
        }

        for (auto p : pairs) {
            str[left] = p[0];
            str[right] = p[1];
            if (str.length() != 1 && str[0] == '0') continue;
            if (left < right || (left == right && p[0] == p[1]))
                dfs(low, high, str, left + 1, right - 1, count, pairs);
        }
    }
};

267 Palindrome Permutation II

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:

Given s = "aabb", return ["abba", "baab"].

Given s = "abc", return [].

class Solution {
public:
    vector<string> generatePalindromes(string s) {
        vector<string> res;
        unordered_map<char, int> char_cnt;
        for (auto c : s) {
            char_cnt[c]++;
        }
        char single;
        int single_cnt = 0;
        for (auto kv : char_cnt) {
            if (kv.second & 1) {
                single = kv.first;
                single_cnt++;
            }
            if (single_cnt > 1) return res;
        }
        string slu;
        if (single_cnt) {
            slu = single;
            char_cnt[single]--;
        }
        string charset;
        for (auto kv : char_cnt) {
            while (kv.second) {
                kv.second -= 2;
                charset += kv.first;
            }
        }

        dfs(charset, res, slu, 0);

        return res;
    }

    void dfs(string charset, vector<string>& res, string slu,int index) {
        if (charset.size() == index) {
            string ret = charset;
            reverse(ret.begin(), ret.end());
            slu = charset + slu + ret;
            res.push_back(slu);
            return;
        }
        for (int i = index; i < charset.size(); ++i) {
            if (i != index && charset[i] == charset[index]) continue;
            swap(charset[i], charset[index]);
            dfs(charset, res, slu, index + 1);
        }
    }
};

results matching ""

    No results matching ""