五个实用的Python案例题,非常有用!

Valid Anagram

问题:给出一个字符串 S,找到在 S 中的最长的回文子串。

LeetCode题目: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.

Valid Palindrome

Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

算法对比:

Valid Palindrome II

  • 暴力枚举法
    • O(N3)
    • 遍历所有子字符串,子串数为 N2,长度平均为 N/2
  • 动态规划法
    • O(N2)
    • 两层循环,外层循环从后往前扫,内层循环从当前字符扫到结尾处,省略已经判断过的记录
  • 中心检测法
    • O(N2)
    • 分奇偶两种情况,以 i 为中心不断向两边扩展判断,无需额外空间
  • 马拉车算法
    • O(N)
    • 从左到右扫描,省略已经判断过的记录,线性

动态规划法

    // DP Solution
    public String longestPalindromeDP(String s) {
        if(s.isEmpty()) return "";

        int n = s.length();
        String result = null;

        // dp[i][j] 表示第i个字符到第j个字符是否为回文
        boolean[][] dp = new boolean[n][n];

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j  ) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i   1][j - 1]);

                if (dp[i][j] && (result == null || j - i   1 > result.length())) {
                    result = s.substring(i, j   1);
                }
            }
        }

        return result;
    }

Valid Parentheses

中心检测法

    // 中心检测法
    public String longestPalindromeCenter(String s) {
        int start = 0, end = 0;

        for (int i = 0; i < s.length(); i  ) {
            /*
            一个回文字符串可以从中心向两边扩展,会有 2n - 1 个中心,而不是 n 个中心。
            因为中心可以存在于两个字符中间,例如 abba,中心在b和b中间。
            */

            // 以第i个字符为中心向两边扩展
            int len1 = expandAroundCenter(s, i, i);

            // 以第i个字符和第i 1个字符的中间为中心向两边扩展
            int len2 = expandAroundCenter(s, i, i   1);

            int len = Math.max(len1, len2);

            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i   len / 2;
            }
        }

        return s.substring(start, end   1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;

        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R  ;
        }

        return R - L - 1;
    }

Manacher's Algorithm 马拉车算法

预处理1:解决字符串长度奇偶问题
马拉车算法可以看成是中心检测法的升级版本,在上面的表格中提到中心检测法是需要区分奇偶两种情况的,那么在马拉车算法中首先要解决的就是这个问题。

这里首先对字符串做一个预处理,在所有的空隙位置(包括首尾)插入同样的符号。无论原字符串是奇数还是偶数,通过这种做法,都会使得处理过的字符串变成奇数长度。

以插入#号为例:
123(长度为3) -> #1#2#3# (长度为7)
abccba (长度为6)-> #a#b#c#c#b#a#(长度为13)

我们把一个回文串中最左或最右位置的字符与其对称轴的距离称为回文半径。
马拉车算法定义了一个回文半径数组 p,用 p[i] 表示以第 i 个字符为对称轴的回文串的回文半径。
例如:

字符串 T = # a # b # a # a # b # a #
半径数组P = 0 1 0 3 0 1 6 1 0 3 0 1 0

Looking at P, we immediately see that the longest palindrome is “abaaba”, as indicated by P6 = 6

为了进一步减少编码的复杂度,可以在字符串的开始加入另一个特殊字符,这样就不用特殊处理越界问题,比如$#a#b#a#

    // Manacher's Algorithm 马拉车算法
    public String longestPalindromeManacher(String s) {
        if (s.length() <= 1) {
            return s;
        }

        // 解决字符串长度奇偶问题
        StringBuilder stringBuilder = new StringBuilder("$");
        for (char c : s.toCharArray()) {
            stringBuilder.append("#");
            stringBuilder.append(c);
        }
        stringBuilder.append("#");
        String str = stringBuilder.toString();

        int id = 0;
        int idMax = 0;
        int index = 0;
        int maxLength = 0;

        int p[] = new int[str.length()];

        // 遍历每一个字符
        for (int curr = 1; curr < str.length(); curr  ) {
            // j 是 curr 关于 id 的对称点
            int j = 2 * id - curr;

            // 如果 idMax > curr,那么P[curr] >= MIN(P[j], idMax - curr)
            if (idMax > curr) {
                if (p[j] < idMax - curr)
                    p[curr] = p[j];
                else
                    p[curr] = idMax - curr;
            } else {
                p[curr] = 1;
            }

            while (curr   p[curr] < str.length() && str.charAt(curr   p[curr]) == str.charAt(curr - p[curr])) {
                p[curr]  ;
            }

            if (curr   p[curr] > idMax) {
                id = curr;
                idMax = curr   p[curr];
            }

            if (p[curr] > maxLength) {
                maxLength = p[curr];
                index = curr;
            }
        }

        return s.substring((index - maxLength) / 2, (index   maxLength) / 2 - 1);
    }

Valid Perfect Square

其他回文字符串题目

LeetCode题目: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".

代码如下,时间复杂度O(n^2)

class Solution {
    public String shortestPalindrome(String s) {
        if(s == null || s.length() <= 1) return s;

        // 找到s中包含第一个字符的最长回文子串
        int right = s.length() - 1;
        while(right > 0 && !isPalindrome(s, 0, right)) {
            right--;
        }
        // 最坏情况 right = 0,例如abc

        StringBuilder sb = new StringBuilder();

        for(int i = s.length() - 1; i > right; i--) {
            sb.append(s.charAt(i));
        }
        sb.append(s);

        return sb.toString();
    }

    public boolean isPalindrome(String s, int start, int end) {
        while(start <= end) {
            if(s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start  ;
            end--;
        }

        return true;
    }
}

对于此题,有时间复杂度为O(n)的算法,利用了 KMP 算法,思路参考https://leetcode.com/articles/shortest-palindrome/,代码如下:

public class Solution {
class Solution {
    public String shortestPalindrome(String s) {
        String temp = s   "#"   new StringBuilder(s).reverse().toString();
        int[] table = getTable(temp);

        return new StringBuilder(s.substring(table[table.length - 1])).reverse().toString()   s;
    }

    public int[] getTable(String s){
        int[] table = new int[s.length()];
        table[0] = 0;

        for(int i = 1; i < s.length(); i  )
        {
            int t = table[i - 1];

            while(t > 0 && s.charAt(i) != s.charAt(t)) {
                t = table[t - 1];
            }

            if(s.charAt(i) == s.charAt(t)) {
                t  ;
            }

            table[i] = t;
        }

        return table;
    }
}

LeetCode题目: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.

class Solution {
    public boolean isPalindrome(String s) {
        // we define empty string as valid palindrome
        if(s.isEmpty()) {
            return true;
        }

        char[] arr = s.toCharArray();

        int i = 0;
        int j = arr.length - 1;

        while(i < j) {
            Character ci = new Character(arr[i]);
            Character cj = new Character(arr[j]);

            // considering only alphanumeric characters
            if(!Character.isDigit(ci) && !Character.isLetter(ci)) {
                i  ;
                continue;
            }

            if(!Character.isDigit(cj) && !Character.isLetter(cj)) {
                j--;
                continue;
            }

            // ignoring cases
            if(Character.toUpperCase(ci) != Character.toUpperCase(cj)) {
                return false;
            }

            i  ;
            j--;
        }

        return true;
    }
}

LeetCode题目:680. Valid Palindrome II
Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:
Input: "aba"
Output: True

Example 2:
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

Note:

  • The string will only contain lowercase characters a-z. The maximum length of the string is 50000.
class Solution {
    public boolean validPalindrome(String s) {
        if(s.isEmpty()) return true;

        int i = 0;
        int j = s.length() - 1;

        while(i < j) {
            if(s.charAt(i) != s.charAt(j)) {
                return validPalindrome(s, i   1, j) || validPalindrome(s, i, j - 1);
            }
            i  ;
            j--;
        }

        return true;
    }

    public boolean validPalindrome(String s, int from, int to) {
        while(from < to) {
            if(s.charAt(from) != s.charAt(to)) {
                return false;
            }
            from  ;
            to--;
        }

        return true;
    }
}

LeetCode题目:266. Palindrome Permutation
Given a string, determine if a permutation of the string could form a palindrome.

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

class Solution {
    public boolean canPermutePalindrome(String s) {
        // key: char, value: count
        Map<Character, Integer> map = new HashMap<>();

        for(char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0)   1);
        }

        // 出现次数为奇数次的字符的个数
        int oddOccur = 0;

        for(Integer count : map.values()) {
            // 出现了奇数次
            if(count % 2 == 1) {
                oddOccur  ;
            }

            if(oddOccur > 1) {
                return false;
            }
        }

        return true;
    }
}

引用:
Manacher's Algorithm 马拉车算法
[Swift 算法] 马拉车算法
Longest Palindromic Substring Part II
Manacher's ALGORITHM: O(n)时间求字符串的最长回文子串

注意,答案只是代表是他人写的代码,正确,但不一定能通过测试(比如超时),列举出来只是它们拥有着独到之处,虽然大部分确实比我的好

1. Valid Anagram

题目

Given two strings s and t, write a function to determine if t is an anagram of s.

For example, 
s = “anagram”, t = “nagaram”, return true. 
s = “rat”, t = “car”, return false.

Note: 
You may assume the string contains only lowercase alphabets.

Follow up: 
What if the inputs contain unicode characters? How would you adapt your solution to such case?

思路与解答

不是很懂啥意思? 
是s和t使用了相同的字符? 
set喽 
好像还要求字符数相等? 
dict呗

1 ds,dt = {},{}
2         for w in s:
3             ds[w] = ds.get(w,0) 1
4         for w in t:
5             dt[w] = dt.get(w,0) 1
6         return ds == dt

答案

啊,我也想过用sorted做。。。但是一闪而过又忘记了?

return sorted(s) == sorted(t)

return all([s.count(c)==t.count(c) for c in string.ascii_lowercase])

return collections.Counter(s)==collections.Counter(t)

真是各种一行方案啊 
看到有人说一个dict就能解决,想了一下是的。

        #是我写的
        d = {}
        for w in s:
            d[w] = d.get(w,0) 1
        for w in t:
            d[w] = d.get(w,0)-1
            if not d[w]:del d[w]
        return not d

2. Valid Palindrome

本文由美洲杯赌球发布于计算机教程,转载请注明出处:五个实用的Python案例题,非常有用!

TAG标签: 美洲杯赌球
Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。