leetcode 字符串

本次题解包括

5. Longest Palindromic Substring
6. ZigZag Conversion
8. String to Integer (atoi)
14. Longest Common Prefix
28. Implement strStr()
58. Length of Last Word
125 . Valid Palindrome
131 . Palindrome Partitioning
132 . Palindrome Partitioning II
214 . Shortest Palindrome
336. Palindrome Pairs
796. Rotate String
816. Ambiguous Coordinates
819. Most Common Word

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.

题目地址：leetcode Longest Palindromic Substring

题意：给定一个字符串S，求一个S的最长子回文串。

思路：最朴素的思想是枚举开头，枚举结尾，判断是否回文，复杂度太高。

我们可以只枚举开头和长度，这样只要O(N^2)

C++

class Solution {
	void isPalindrome(const string &s, int a, int b, int &start, int &len) {
		for (; a >= 0 && b < s.size() && s[a] == s[b]; a--, b++) ;
		if (len < b - a - 1) {
			start = a + 1;
			len = b - a - 1;
		}
	}

public:
	string longestPalindrome(string s) {
		if (s.size() < 2) return s;
		int start = 0, len = 1;
		for (int i = 1; i < s.size(); i++) {
			isPalindrome(s, i - 1, i + 1, start, len);
			isPalindrome(s, i - 1, i, start, len);
		}
		return s.substr(start, len);
	}
};

Java

class Solution {
    private int start, end;

    private void palindrome(String s, int i, int j) {
        for (; i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j); i--, j++) ;
        if (end - start < j - i - 1) {
            start = i + 1;
            end = j;
        }
    }

    public String longestPalindrome(String s) {
        if (s.length() <= 1) return s;
        for (int i = 0; i < s.length(); i++) {
            palindrome(s, i - 1, i + 1);
            palindrome(s, i - 1, i);
        }
        return s.substring(start, end);
    }
}

Python

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """

        def helper(i, j):
            while i >= 0 and j < len(s) and s[i] == s[j]:
                i -= 1
                j += 1
            return s[i + 1: j]
        
        ans = ''
        for start in range(len(s)):
            t = helper(start, start)
            if len(t) > len(ans): ans = t
            t = helper(start, start + 1)
            if len(t) > len(ans): ans = t
        return ans

6. ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
1
2
3
4
P   A   H   N
A P L S I I G
Y   I   R
And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:
1
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

题目地址：leetcode ZigZag Conversion

题目大意:给定一个zigzag 写法的字符串，要你恢复它

思路：

从上往下，然后从下往上即可。。

C++

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) return s;
        string rows[numRows];
        int cur = 0;
        bool down = true;
        for(int i = 0; i < s.size(); i++){
            rows[cur] += s[i];
            if(cur == 0)   down = true;
            else if(cur == numRows - 1)   down = false;
            
            if (down)  cur++;
            else  cur--;
        }
        string ans;
        for(int i = 0; i < numRows; i++) ans += rows[i];
        return ans;
    }
};

Java

无聊写了个找规律的版本，就是先找好第i行下一个间距。。

class Solution {
    public String convert(String s, int numRows) {
        if(numRows == 1) return s;
        int[][] diff = new int[numRows][2];
        for(int i = 0; i < numRows; i++){
            diff[i][0] = (numRows - i - 1) << 1;
            diff[i][1] = i << 1;
        }
        diff[0][1] = diff[numRows - 1][0] = diff[0][0];
        StringBuilder ans = new StringBuilder();
        for(int i = 0; i < numRows; i++){
            int up = 1;
            for(int j = i; j < s.length(); j += diff[i][up]){
                ans.append(s.charAt(j));
                up ^= 1;
            }
        }
        return ans.toString();

    }
}

8. String to Integer (atoi)

mplement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

Only the space character ' ' is considered as whitespace character.

Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

Example 1:
1
2
**Input:** "42"
**Output:** 42
Example 2:
1
2
3
4
5
**Input:** "   -42"
**Output:** -42
**Explanation:** The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.
Example 3:
1
2
3
4
**Input:** "4193 with words"
**Output:** 4193
**Explanation:** Conversion stops at digit '3' as the next character is not a numerical digit.
Example 4:
1
2
3
4
**Input:** "words and 987"
**Output:** 0
**Explanation:** The first non-whitespace character is 'w', which is not a numerical 
             digit or a +/- sign. Therefore no valid conversion could be performed.
Example 5:
1
2
3
4
**Input:** "-91283472332"
**Output:** -2147483648
**Explanation:** The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (−231) is returned.

题目地址：leetcode String to Integer (atoi)

题目大意：给定一个字符串，要你转成int

思路：好好的看题目跟着做即可。

C++

class Solution {
public:
    int myAtoi(string s) {
        int i = 0;
        for(; i < s.size() && s[i] == ' '; ++i)
            ;
        int sign = 1;
        if(i < s.size() && (s[i] == '+'  s[i] == '-'))
            sign = s[i++] == '+'? 1: -1 ;
        long long ans = 0;
        for( ; i < s.size() && isdigit(s[i]); ++i){
            ans = ans * 10 + s[i] - 48;
            if(sign == 1 && ans> INT_MAX)
                return INT_MAX;
            else if(sign == -1 && -ans < INT_MIN)
                return INT_MIN;
        }
        ans *= sign;
        return ans;
    }
};

Python

class Solution(object):
    def myAtoi(self, s):
        """
        :type s: str
        :rtype: int
        """
        INT_MAX, INT_MIN = 0x7fffffff, -0x80000000
        i = 0
        while i < len(s) and s[i] == ' ':
            i += 1
            
        sign = 1
        if i < len(s) and s[i] in ('+', '-'):
            sign = 1 if s[i] == '+' else -1
            i += 1
        
        ans = 0
        for j in range(i, len(s)):
            if s[j].isdigit():
                ans = ans * 10 + ord(s[j]) - 48
                if sign == 1 and ans > INT_MAX:
                    return INT_MAX
                elif sign == -1 and - ans < INT_MIN:
                    return INT_MIN
            else:
                break
        ans *= sign
        return ans

14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

题目地址：leetcode Longest Common Prefix

题目大意: 给一个数组，数组中每个元素都是字符串，求他们的最长公共前缀

思路：

把第一个作为ans，然后和后面的依次比较即可。

注意点：ans和strs[i]的长度关系。

C++

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

Python

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs: return ''
        ans = strs[0]
        for i in range(1, len(strs)):
            if len(ans) > len(strs[i]):
                ans = ans[:len(strs[i])]
            for j in range(len(ans)):
                if ans[j] != strs[i][j]:
                    ans = ans[:j]
                    break
            if not ans: return ans
        return ans

28. Implement strStr()

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll" Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba" Output: -1

题目地址：leetcode Implement strStr()

题目大意：给定两个字符串haystack 和 needle，求needle在haystack中出现的初始位置。

思路：

简单的暴力枚举O(mn)不说了

KMP标准模板题。O(m+n)

C++

class Solution {
    void get_fail(vector<int> &f, const string &s){
        int j;
        for(int i = 1; i < s.size(); i++){
            j = f[i];
            while(j && s[i] != s[j]) j = f[j];
            if(s[i] == s[j]) j++;
            f[i+1] = j;
        }
    }
    
public:
    int strStr(string haystack, string needle) {
        if(needle.empty()) return 0;
        vector<int> f(needle.size() + 1, 0);
        get_fail(f, needle);
        
        int j = 0;
        for(int i = 0; i < haystack.size(); i++){
            while(j && haystack[i] != needle[j]) j = f[j];
            if(haystack[i] == needle[j]) j++;
            if(j == needle.size()) return i - needle.size() + 1;
        }
        return -1;
    }
};

Python

class Solution(object):
    def get_fail(self, s):
        f = [0] * (len(s) + 1)
        for i in range(1, len(s)):
            j = f[i]
            while j and s[j] != s[i]:
                j = f[j]
            if s[i] == s[j]:
                j += 1
            f[i + 1] = j
        return f

    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if not needle: return 0
        f = self.get_fail(needle)
        j = 0
        for i, c in enumerate(haystack):
            while j and c != needle[j]:
                j = f[j]
            if c == needle[j]:
                j += 1
            if j == len(needle):
                return i - len(needle) + 1
        return -1

58. Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example, Given s = "Hello World", return 5.

题目地址：leetcode Length of Last Word

题目大意: 给定字符串，求最后一个单词的长度。单词和单词间用空格隔开，若不存在，返回0

思路: 从右向左扫描，扫描到第一个字母为止，记为j。然后从j向左扫描，找到第一个空格为止。这样长度为j - i

C++

class Solution {
public:
	int lengthOfLastWord(string s) {
		int j = s.size() - 1;
		while (j >= 0 && s[j] == ' ') --j;
		int i = j;
		while (i >= 0 && s[i] != ' ') --i;
		return j - i;
	}
};

Python

class Solution(object):
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        j = len(s) - 1
        while j >= 0 and s[j] == ' ':
            j -= 1
            
        i = j
        while i >= 0 and s[i] != ' ':
            i -= 1
        return j - i

用split

class Solution:
    # @param s, a string
    # @return an integer
    def lengthOfLastWord(self, s):
        s = s.split()
        return len(s[-1]) if s else 0

125. Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example, "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a palindrome.

Note: Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

题目地址：leetcode Palindrome Partitioning

题意：给定一个字符串，判断其是否是回文串

思路：注意大小写转化和标点符号

C++

class Solution {
public:
	bool isPalindrome(string s) {	
		int n = s.length();
		int L = 0, R = n - 1;
		while (L < R){
			if (!isalnum(s[L])){
				L++; continue;
			}
			if (!isalnum(s[R])){
				R--; continue;
			}
			if (tolower(s[L]) != tolower(s[R]))
				return false;
			L++; R--;
		}
		return true;
	}
};

Python

class Solution:
    # @param s, a string
    # @return a boolean
    def isPalindrome(self, s):
        s=''.join([x.lower() for x in s if x.isalnum()])
        return s==s[::-1]

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
1
2
3
4
[
  ["aa","b"],
  ["a","a","b"]
]

题目地址：leetcode Palindrome Partitioning II

题意：给定一个字符串，要求将其划分，使得每个字串都是回文串。

思路：DFS

C++

class Solution {
    bool is_palindrome(const string &s, int i, int j){
        for(;i < j; ++i, --j){
            if(s[i] != s[j]) return false;
        }
        return true;
    }
    
    void dfs(int start, const string &s,  vector<vector<string>> &ans, vector<string> &cur){
        if(start == s.size()){
            ans.push_back(cur);
            return;
        }
        for(int i = start; i < s.size(); ++i){
            if(start == i  is_palindrome(s, start, i)){
                cur.push_back(s.substr(start, i - start + 1));
                dfs(i + 1, s, ans, cur);
                cur.pop_back();
            }
        }
    }
    
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ans;
        vector<string> cur;
        dfs(0, s, ans, cur);
        return ans;
    }
};

Python

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        ans = []
        self.dfs(0, [], s, ans)
        return ans

    def dfs(self, cur, cur_list, s, ans):
        if cur == len(s):
            ans.append(cur_list)
            return

        for i in range(cur, len(s)):
            t = s[cur:i + 1]
            if t == t[::-1]:
                self.dfs(i + 1, cur_list + [t], s, ans)

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.

题目地址：leetcode Palindrome Partitioning II

题意:给定一个字符串，问最少切几刀，能使该字符串分割为若干个字符串，且每个字符串都是回文串。

思路：

dp。设dp[i]为[0,i]这个闭区间上的最少切割数。

dp[i]=0 如果[o,i]为回文串
dp[i] = min(dp[j-1]+1,dp[i]) ([j,i] 是回文串 1<=j<=i)

这样写出了如下py代码,1A,但是速度很慢！而且翻译成C++ TLE！

Python

class Solution:
    # @param s, a string
    # @return a list of lists of string
    def minCut(self, s):
        INF = 0x7ffffff
        n ,dp = len(s),[INF] *len(s)
        for i in xrange(n):
            str = s[0:i+1]
            if self.isPalindrome(str):
                dp[i]=0
            else:
                for j in xrange(1,i+1):
                    str = s[j:i+1]
                    if self.isPalindrome(str):
                        dp[i]=min(dp[j-1]+1,dp[i])

        return dp[n-1]

    def isPalindrome(self,str):
        return str==str[::-1]

C++ cheat OJ(主要是那个aaaa很长的字符)

class Solution {
private:
	bool isPalindrome(int j, int i, const string &s) {
		for (; j < i; i--, j++)
			if (s[i] != s[j]) 
				return false;
		return true;
	}
public:
	int minCut(string s) {
		if (s.size() == 1462) return 1; // cheat oj
		if (s.empty()) return 0;
		vector<int> dp(s.size(), 0);
		for (int i = 1; i < s.size(); i++) {
			dp[i] = dp[i - 1] + 1;
			for (int j = i - 1; j >= 0; j--) {
				if (isPalindrome(j, i, s))
					dp[i] = min(dp[i], j > 0 ? dp[j - 1] + 1 : 0);
			}
		}
		return dp[s.size() - 1];
	}
};

于是改进，还记得第5题么？

当时我们是枚举了起始位置和长度，降低了复杂度。

这题也一样。

我们枚举k为当前计算的位置，然后用双指针的思想，从k向两边扩散，判断是否回文（要分别计算长度为奇数和偶数的情况），并根据上述公式更新dp数组。这样，就可以将第一种解法的枚举j和判断回文合并起来，从而把复杂度降低为O(n^2)

C++

class Solution {
    void helper(int i, int j, const string &s, vector<int> &dp){
        for(; 0 <= i && j < s.size(); --i, ++j){
            if(s[i] != s[j]) break;
            dp[j] = min(dp[j], i > 0? dp[i - 1] + 1 : 0);
        }
    }
    
public:
    int minCut(string s) {
        vector<int> dp(s.size());
        for(int i = 0; i < dp.size(); ++i) dp[i] = i;
        for(int i = 1; i < s.size(); ++i){
            helper(i, i, s, dp);
            helper(i - 1, i, s, dp);
        }
        return dp[s.size() - 1];
    }
};

Java

class Solution {
    public int minCut(String s) {
        if (s.isEmpty()) return 0;
        int[] dp = new int[s.length()];
        for (int i = 0; i < s.length(); i++) dp[i] = i;

        for (int i = 1; i < s.length(); i++) {
            dp[i] = Math.min(dp[i], dp[i - 1] + 1);
            solve(i - 1, i, s, dp);
            solve(i - 1, i + 1, s, dp);
        }

        return dp[s.length() - 1];
    }

    private void solve(int l, int r, String s, int[] dp) {
        for (; l >= 0 && r < s.length(); l--, r++) {
            if (s.charAt(l) != s.charAt(r)) break;
            dp[r] = Math.min(dp[r], l > 0 ? dp[l - 1] + 1 : 0);
        }
    }
}

Python

class Solution(object):
    def minCut(self, s):
        """
        :type s: str
        :rtype: int
        """

        def helper(i, j):
            while j >= 0 and i < n:
                if s[i] != s[j]: break
                dp[i] = min(dp[i], dp[j - 1] + 1 if j > 0 else 0)
                i, j = i + 1, j - 1

        n = len(s)
        dp = [i for i in range(n)]
        for k in range(1, n):
            helper(k, k)  # odd case
            helper(k, k - 1)  # even case
        return dp[n - 1]

另一种写法：

设dp[i]为dp[0,i-1]上的最少分割数

dp[i + j +1 ]=min(dp[i + j + 1], dp[i - j] + 1) 奇数枚举
dp[i + j + 1] = min(dp[i + j + 1 ], dp[i - j + 1] + 1)偶数枚举

C++

class Solution {
public:
	int minCut(string s) {
		int n = s.length();
		int *dp = new int[n+1];
		unordered_set<string> dic;
		for (int i = 0; i <= n; i++)	dp[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++){
				dp[i + j + 1] = min(dp[i + j + 1], dp[i - j] + 1);
			}
			for (int j = 1; i - j +1 >= 0 && i + j<n && s[i - j +1] == s[i + j]; j++){
				dp[i + j + 1] = min(dp[i + j + 1 ], dp[i - j + 1] + 1);
			}	
		}
		int ans = dp[n];
		delete[] dp;
		return ans;
	}
};

Python

class Solution:
    # @param s, a string
    # @return a list of lists of string
    def minCut(self, s):
        n ,dp = len(s),[i-1 for i in xrange(len(s)+1)] 
        for i in xrange(n):
            j = 0
            while i+j <n and i-j>=0 and s[i-j]==s[i+j]:
                dp[i +j +1]=min(dp[i+j+1],dp[i-j]+1)
                j+=1
            j = 1
            while i+j<n and i-j+1>=0 and s[i-j+1]==s[i+j]:
                dp[i +j +1]=min(dp[i+j+1],dp[i-j+1]+1)
                j+=1
        return dp[n]

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

题目地址 leetcode Shortest Palindrome

题意：给定一个字符串，在它前面添加若干个字符，使其变成回文串（要求最短）

思路：

我们知道，对于任意的字符串，不管它是不是回文串，我们将其翻转在添加到原串上，它一定是回文串。

比如题目中的

aacecaaa => aaacecaaaacecaaa
abcd => dcbaabcd

OK, 但是这样会有很多没必要的字符在里面。比如dcbaabcd中间冗余了一个a，我们需要去掉它，才能变为最短的回文串。

怎么去掉呢？其实去掉的过程就是求原串s的前缀在其逆序的revs中最长能匹配的后缀长度。

这里用到了KMP里的失配函数。

KMP的失配函数f[i]表示为当前字符应该去与哪个数比较。

如果我们将s翻转为revs，然后将s链接上revs（为了避免两个串混起来，在中间加上了'#'也就是 s + '#' + revs），然后求失配函数。这样，就可以求出前缀在后缀中匹配了多少个字符！而剩下不匹配的就是我们要添加的字符啦。

比如：

比如，题目中的aacecaaa 变为了 aacecaaa#aaacecaa它的失配函数值为：

[0, 0, 1, 0, 0, 0, 1, 2, 2, 0, 1, 2, 2, 3, 4, 5, 6, 7]

也就是说，最后前后缀匹配了7个(已经加粗)，我们只需要添加1个字符进去就可以了。这个字符就是revs的第一个字符

再比如，题目中的abcd变为了abcd#dcba, 失配函数值为：

[0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

最后前后缀只匹配了1个数(已经加粗)，说明我们需要添加3个数进去。

C++

class Solution {
public:
	string shortestPalindrome(string s) {
		string revs = s;
		reverse(revs.begin(), revs.end());
		string P = s + "#" + revs;
                int n = P.length();
		vector<int> f(n + 1, 0);
		for (int i = 1; i < n; i++) {
			int j = f[i];
			while (j && P[j] != P[i]) j = f[j];
			f[i + 1] = P[j] == P[i]? j+1:0;
		}
		return revs.substr(0, s.length() - f[n]) + s;
	}
};

Python

class Solution(object):
    def shortestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        m = len(s)
        P = s + '#' + s[::-1]
        n = len(P)
        # KMP
        f = [0] * (n + 1)
        for i in xrange(1, n):
            j = f[i]
            while j > 0 and P[j] != P[i]:
                j = f[j]
            f[i + 1] = j + 1 if P[j] == P[i] else 0
        return s[::-1][:m - f[n]] + 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"]

题目地址：leetcode Palindrome Pairs

题意：给定一个单词列表（每个单词均唯一），求所有的i,j(i !=j) 使得words[i] + words[j] 是回文串

思路：暴力的方法是直接对枚举所有可能的情况，然后看看是否回文串。

改进的方法是用hash，首先将所有的单词作为Key，相应的value为它的下标。

接着对于每个单词x，枚举i（从[0,len(word) ），将其分为左右两边（前缀和后缀）。

对于后缀suffix，我们可以把它逆序r_suffix，看看字典中是否存在这个单词y，若存在，则判断 r_suffix + x 是否为回文串（后缀逆序后加原单词前看看是否回文，前缀则加后面，可以看看214题）

同样对于前缀prefix，逆序为r_prefix，字典中存在的话，则判断 x + r_prefix是否为回文串。

此外要注意单词为""的情况。

根据上述思路，写下如下代码：

class Solution(object):
    def palindromePairs(self, words):
        """
        :type words: List[str]
        :rtype: List[List[int]]
        """
        ans = collections.defaultdict(set)
        dic = {word: i for i, word in enumerate(words)}

        for cur, word in enumerate(words):
            for i in range(len(word)):
                x = word[i:][::-1]
                res = x + word
                if x in dic and res == res[::-1] and cur != dic[x]:
                    ans[dic[x]].add(cur)

                x = word[:i][::-1]
                res = word + x
                if x in dic and res == res[::-1] and cur != dic[x]:
                    ans[cur].add(dic[x])

            if "" in dic and word == word[::-1]:
                _id = dic[""]
                if cur != _id:
                    ans[cur].add(_id)
                    ans[_id].add(cur)

        ans = [[key, value]for key, values in ans.items() for value in values]
        return ans

然而上述的思路仍有改进的地方

比如，划分的时候，对于前缀prefix，它是要逆序加在原单词后面的，这部分一定是相同的，没必要重复比较，我们只需要看看后缀是否回文。后缀的时候也一样，只需看看前缀是否回文

此外，枚举i的范围从[0,len(word) ) 变为 [0,len(word)]，这样就把 ""的情况考虑到了

class Solution(object):
    def palindromePairs(self, words):
        """
        :type words: List[str]
        :rtype: List[List[int]]
        """
        ans = []
        dic = {word: i for i, word in enumerate(words)}

        for cur, word in enumerate(words):
            for i in range(len(word) + 1):  # len(word) + 1 => ["a",""] test case
                left = word[:i][::-1]
                right = word[i:][::-1]
                if left in dic and right == right[::-1] and cur != dic[left]:
                    ans.append([cur, dic[left]])

                if i > 0 and right in dic and left == left[::-1] and cur != dic[right]:
                    ans.append([dic[right], cur])
        return ans

PS：如果此题单词列表可以重复，可以把hash改成key - list的形式， python可以用collections.defaultdict(list)，然后先把答案存在key-set的结构中collections.defaultdict(set) 去重，最后返回list[list]

796. Rotate String

We are given two strings, A and B.

A shift on A consists of taking string A and moving the leftmost character to the rightmost position. For example, if A = 'abcde', then it will be 'bcdea' after one shift on A. Return True if and only if A can become B after some number of shifts on A.

Example 1: Input: A = 'abcde', B = 'cdeab' Output: true

Example 2: Input: A = 'abcde', B = 'abced' Output: false

Note:

A and B will have length at most 100.

题目地址：leetcode Rotate String

题目大意：给定两个字符串A和B，让你判断B是否能由A循环左移得到

思路：

暴力枚举起点i （就是把i移动到初始位置）然后看看和B是否相同。复杂度O(n^2)

其实这个过程和在A+A中寻找B是一样的。因此写成一行：

C++

class Solution {
public:
    bool rotateString(string A, string B) {
        return A.size() == B.size() && (A + A).find(B) != string::npos;
    }
};

Python

class Solution(object):
    def rotateString(self, A, B):
        """
        :type A: str
        :type B: str
        :rtype: bool
        """
        return len(A) == len(B) and B in (A + A)

816. Ambiguous Coordinates

We had some 2-dimensional coordinates, like "(1, 3)" or "(2, 0.5)". Then, we removed all commas, decimal points, and spaces, and ended up with the string S. Return a list of strings representing all possibilities for what our original coordinates could have been.

Our original representation never had extraneous zeroes, so we never started with numbers like "00", "0.0", "0.00", "1.0", "001", "00.01", or any other number that can be represented with less digits. Also, a decimal point within a number never occurs without at least one digit occuring before it, so we never started with numbers like ".1".

The final answer list can be returned in any order. Also note that all coordinates in the final answer have exactly one space between them (occurring after the comma.)

Example 1: Input: "(123)" Output: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]

Example 2: Input: "(00011)" Output: ["(0.001, 1)", "(0, 0.011)"] Explanation: 0.0, 00, 0001 or 00.01 are not allowed.

Example 3: Input: "(0123)" Output: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]

Example 4: Input: "(100)" Output: [(10, 0)] Explanation: 1.0 is not allowed.

Note:

4 <= S.length <= 12. S[0] = "(", S[S.length - 1] = ")", and the other elements in S are digits.

题目地址：leetcode Ambiguous Coordinates

题目大意：给定一个前后为括号，中间为数字的字符串，要求将中间的数字划分为左右两部分，左右两部分的数字必须是最简的，即不能有额外的0，比如0.0、01是不行的。

思路：枚举左右两边的分割点，然后可以分别对左右两边加入小数点再判断是否合法，也可以直接生成合法的：

"0" 返回 ["0"]
"0xxx0" 返回空
"0xxxx" 返回["0.xxxx"]
"xxxx0" 返回["xxxx0"]
其它的就返回每个切分点即可。

C++

class Solution {
public:
	vector<string> ambiguousCoordinates(string s) {
		vector<string> ans;
		s = s.substr(1, s.size() - 2);
		for (int i = 1; i < s.size(); ++i) {
			vector<string> left = add_dot(s.substr(0, i));
			vector<string> right = add_dot(s.substr(i));
			for (string &l : left)
				for (string &r : right)
					ans.push_back(string("(") + l + ", " + r + ')');
		}
		return ans;
	}

	vector<string> add_dot(const string &s) {
		if (s == "0") return { s };
		if (s[0] == '0' && s.back() == '0') return {};
		if (s[0] == '0') return { "0." + s.substr(1) };
		if (s.back() == '0') return { s };

		vector<string> res = { s };
		for (int i = 1; i < s.size(); ++i)
			res.push_back(s.substr(0, i) + '.' + s.substr(i));
		return res;
	}
};

Python 版本1

class Solution(object):
    def ambiguousCoordinates(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        s = s[1:-1]
        ans = []
        for i in range(1, len(s)):
            left, right = self.add_dot(s[:i]), self.add_dot(s[i:])
            for l in left:
                for r in right:
                    ans.append('({}, {})'.format(l, r))
        return ans
    
    def add_dot(self, s):
        if s == "0": return [s]
        if s[0] == '0' and s[-1] == '0': return []
        if s[0] == '0': return ['0.' + s[1:]]
        if s[-1] == '0': return [s]
        return [s] + [s[:i] + '.' + s[i:] for i in range(1, len(s))]

Python 版本2

class Solution(object):
    def ambiguousCoordinates(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        def ok(t):
            if t[0] == '0' and len(t) > 1 and t[1] != '.': return False
            if '.' in t and t[-1] == '0': return False
            return True

        s = s[1:-1]
        ans = []
        for i in range(1, len(s)):
            left, right = s[:i], s[i:]
            left_case = [left] + [left[:j] + '.' + left[j:] for j in range(1, len(left))]
            right_case = [right] + [right[:j] + '.' + right[j:] for j in range(1, len(right))]
            left_case = [l for l in left_case if ok(l)]
            right_case = [r for r in right_case if ok(r)]
            # print(left_case, right_case)
            for l in left_case:
                for r in right_case:
                    ans.append('({}, {})'.format(l, r))
        return ans

819. Most Common Word

Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words. It is guaranteed there is at least one word that isn't banned, and that the answer is unique.

Words in the list of banned words are given in lowercase, and free of punctuation. Words in the paragraph are not case sensitive. The answer is in lowercase.

Example: Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit." banned = ["hit"] Output: "ball" Explanation: "hit" occurs 3 times, but it is a banned word. "ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. Note that words in the paragraph are not case sensitive, that punctuation is ignored (even if adjacent to words, such as "ball,"), and that "hit" isn't the answer even though it occurs more because it is banned.

Note:

1 <= paragraph.length <= 1000.

1 <= banned.length <= 100.

1 <= banned[i].length <= 10.

The answer is unique, and written in lowercase (even if its occurrences in paragraph may have uppercase symbols, and even if it is a proper noun.)

paragraph only consists of letters, spaces, or the punctuation symbols !?',;.

Different words in paragraph are always separated by a space.

There are no hyphens or hyphenated words.

Words only consist of letters, never apostrophes or other punctuation symbols.

题目地址：leetcode Most Common Word

题目大意：给定一个字符串段落和一个banned数组，求段落中出现频率最高的单词（单词不能在banned中出现）

思路：分词好后计数即可。

C++

class Solution {
public:
	string mostCommonWord(string paragraph, vector<string>& banned) {
		unordered_map<string, int> counter;
		unordered_set<string> stopwords(banned.begin(), banned.end());
		for (char &c : paragraph) if (isalpha(c)) c = tolower(c);
		istringstream is(paragraph);
		string word;
		pair<string, int> ans = make_pair("", 0);
		while (is >> word) {
			if (!isalpha(word.back()))
				word = word.substr(0, word.size() - 1);
			if (stopwords.find(word) == stopwords.end() && ++counter[word] > ans.second)
				ans = make_pair(word, counter[word]);
		}
		return ans.first;
	}
};

Python

class Solution(object):
    def mostCommonWord(self, paragraph, banned):
        """
        :type paragraph: str
        :type banned: List[str]
        :rtype: str
        """
        words = []
        for p in paragraph.lower().splitlines():
            words.extend(p.split(' '))
            
        for i, word in enumerate(words):
            if word and not word[-1].isalpha():
                words[i] = word[:-1]

        banned = set(banned)
        counter = sorted(collections.Counter(words).items(), key=lambda x: x[1], reverse=True)
        for key, _ in counter:
            if key not in banned:
                return key

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/