Leetcode|字符串

豆知识⁍

1. 比较函数⁍

可以用 “==” 来比较两个字符串吗？

取决于使用的语言是否支持运算符重载？

如果答案是 yes （例如 C++、Python）。我们可以使用 == 来比较两个字符串；

如果答案是 no （例如 Java），我们可能无法使用 == 来比较两个字符串。当我们使用 == 时，它实际上会比较这两个对象是否是同一个对象。(可以用 string.equals和string.compareTo)

// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        // initialize
        String s1 = "Hello World";
        System.out.println("s1 is \"" + s1 + "\"");
        String s2 = s1;
        System.out.println("s2 is another reference to s1.");
        String s3 = new String(s1);
        System.out.println("s3 is a copy of s1.");
        // compare using '=='
        System.out.println("Compared by '==':");
        // true since string is immutable and s1 is binded to "Hello World"
        System.out.println("s1 and \"Hello World\": " + (s1 == "Hello World"));
        // true since s1 and s2 is the reference of the same object
        System.out.println("s1 and s2: " + (s1 == s2));
        // false since s3 is refered to another new object
        System.out.println("s1 and s3: " + (s1 == s3));
        // compare using 'equals'
        System.out.println("Compared by 'equals':");
        System.out.println("s1 and \"Hello World\": " + s1.equals("Hello World"));
        System.out.println("s1 and s2: " + s1.equals(s2));
        System.out.println("s1 and s3: " + s1.equals(s3));
        // compare using 'compareTo'
        System.out.println("Compared by 'compareTo':");
        System.out.println("s1 and \"Hello World\": " + (s1.compareTo("Hello World") == 0));
        System.out.println("s1 and s2: " + (s1.compareTo(s2) == 0));
        System.out.println("s1 and s3: " + (s1.compareTo(s3) == 0));
    }
}

output

s1 is “Hello World”
s2 is another reference to s1.
s3 is a copy of s1.
Compared by ‘==’:
s1 and “Hello World”: true
s1 and s2: true
s1 and s3: false
Compared by ‘equals’:
s1 and “Hello World”: true
s1 and s2: true
s1 and s3: true
Compared by ‘compareTo’:
s1 and “Hello World”: true
s1 and s2: true
s1 and s3: true

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/array-and-string/c9lnm/
来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

最长公共前缀 ⁍

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

思路：

python 高阶(?)用法
1. 使用zip将每个str的第i个字符结合形成元组，即(strs[0][0],strs[1][0],strs[2][0],...)
2. 用set排除每个元组中重复的元素，如果只剩一个元素，证明是公共的字母

循环直到不是只剩一个元素的情况，说明公共前缀已经结束，退出循环

作者：Muzi-Li
链接：https://leetcode-cn.com/leetbook/read/array-and-string/ceda1/?discussion=TZS629

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        ret = ''
        #使用zip
        for i in zip(*strs):
            if len(set(i)) == 1:
             ret += i[0]
            else:
                break
        return ret

其他的（待更新）

5. 最长回文子串 ⁍

给你一个字符串 s，找到 s 中最长的回文子串。

思路：

中心扩展，分奇偶

class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = ""
        for i in range(len(s)):
            s1 = self.findPalindrome(s , i, i)
            s2 = self.findPalindrome(s, i, i+1)
            res = res if len(res)>len(s1) else s1
            res = res if len(res)>len(s2) else s2
        return res


    def findPalindrome(self, s, l, r):
        '''
            寻找以l为中心扩散的最长回文子串；
            偶串的情况：r=l+1
            奇串的情况：r=l
        '''
        while l>=0 and r<len(s) and s[l]==s[r]:
            l-=1
            r+=1
        return s[l+1:r]

↓相似题：

647. 回文子串 ⁍

class Solution:
    def __init__(self):
        self.res = 0
    def countSubstrings(self, s: str) -> int:
        for i in range(1, len(s)):
            self.countFromIJ(s,i-1,i-1)
            self.countFromIJ(s,i-1,i)
        self.res += 1 # 加上s[-1]
        return self.res
    
    def countFromIJ(self, s, left, right):
        '''
            从left,right中心扩散
            当s的长度为偶数时，right事实上=left+1
            ..........奇数时，right=left
        '''
        while left>=0 and right<=len(s)-1 and s[left]==s[right]:
            self.res+=1
            left-=1
            right+=1