Tag: String

Posted 2022-04-27Updated 2022-06-25LeetCode / Medium / 复习2 minutes read (About 353 words)

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

并查集，注意要使用路径压缩否则会超时。
先将所有配对联通。然后创建一个数组group记录每个字符串位置的分组情况。
根据分组，借助优先队列保存字符串。
通过哈希表创建group和PriorityQueue的映射。
按当前位置的分组情况和优先队列的顺序来添加字符串。
最后返回字符串。

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        StringBuffer sb = new StringBuffer();
        UnionFind uf = new UnionFind(s.length());
        
        for(List<Integer> pair : pairs){
            uf.union(pair.get(0), pair.get(1));    
        }
        
        int[] group = new int[s.length()];
        for(int i = 0; i < s.length(); i++){
            group[i] = uf.find(i);
        }
        
        HashMap<Integer, PriorityQueue<Character>> map = new HashMap<>();
        
        for(int i = 0; i < s.length(); i++){
            PriorityQueue<Character> bin = map.getOrDefault(group[i], new PriorityQueue<Character>());
            bin.add(s.charAt(i));
            map.put(group[i], bin);
        }
        for(int i = 0; i < s.length(); i++){
            sb.append(map.get(group[i]).poll());
        }
        return sb.toString();
    }
    
    class UnionFind {
        int[] parent;
        int[] count;
        public UnionFind(int n){
            parent = new int[n];
            count = new int[n];
            for(int i = 0; i < n; i++){
                parent[i] = i;
                count[i] = 1;
            }
        } 
        
        private int find(int id){
            if(parent[id] == id) return id;
            parent[id] = find(parent[id]);
            return parent[id];
        }
        
        private boolean union(int id1, int id2){
            int p1 = find(id1);
            int p2 = find(id2);
            if(p1 == p2) return false;
            if(count[p1] > count[p2]) parent[p2] = p1;
            else parent[p1] = p2;
            return true;
        }
    }
}

Posted 2022-04-24Updated 2022-04-24LeetCode / Medium / 复习2 minutes read (About 351 words)

187. Repeated DNA Sequences

The DNA sequence is composed of a series of nucleotides abbreviated as ‘A’, ‘C’, ‘G’, and ‘T’.

For example, “ACGAATTCCG” is a DNA sequence.
When studying DNA, it is useful to identify repeated sequences within the DNA.

Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.

哈希表 + 滑动窗口 + 位操作。
将四个字符映射到四个二进制字符上。这样字符串就可以用20bit表示。
这样就可以用一个整数来表示这四个字符。
然后采用哈希表记录出现次数。

class Solution {
    static final int L = 10;
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ret = new ArrayList<String>();
        if(s.length() < L) return ret;
        HashMap<Integer, Integer> map = new HashMap<>();
        int left = 0;
        int right = 10;
        
        int[] bin = new int[26];
        bin['A'-'A'] = 0;
        bin['T'-'A'] = 1;
        bin['C'-'A'] = 2;
        bin['G'-'A'] = 3;
        
        int x = 0;
        for(int i = 0; i < L-1; i++){
            x = (x << 2) | bin[s.charAt(i)-'A'];
        }
        
        for(int i = 0; i <= s.length() - L; i++){
            x = ((x << 2) | bin[s.charAt(i + L -1)-'A']) & ((1 << L * 2) - 1);
            map.put(x, map.getOrDefault(x, 0)+1);
            if(map.get(x) == 2) ret.add(s.substring(i, i+L)); 
        }
        return ret;
    }
}

遍历将字字符串加入哈希表并记录出现次数，然后返回出现次数大于1的字符串。
注意在循环时就可以直接添加结果到列表，这样可以减少操作。

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ret = new ArrayList<String>();
        HashMap<String, Integer> map = new HashMap<>();
        int left = 0;
        int right = 10;
        
        while(right <= s.length()){
            String sub = s.substring(left, right);
            map.put(sub, map.getOrDefault(sub, 0)+1);
            if(map.get(sub) == 2) ret.add(sub); 
            left++;
            right++;
        }
        return ret;
    }
}

Posted 2022-04-24Updated 2022-06-08LeetCode / Medium / 复习8 minutes read (About 1136 words)

5. Longest Palindromic Substring

Question

Given a string s, return the longest palindromic substring in s.

Solution

马拉车算法，专门用于计算最大回文子字符串长度。

预处理

首先需要对字符串进行预处理，将每两个字符之间（包括两端）加上一个符号’#’。
然后在字符串的前后加入任意两个不同的符号。（防止中心扩展时继续搜索）

这个操作使得偶数项的回文字符串变为奇数项的回文字符串，便于接下来进行统一的中心扩展操作。

Manacher算法

参考资料：一文让你彻底明白马拉车算法

用一个数组p[]记录处理后字符串位置的中心展开长度。

初始化一个回文中心的下标位置i，和当前回文中心的右侧范围r。
在进行算法时维护这两个参数。

遍历字符串中除了首尾两个字符以外的位置。

初始化i位置关于c的镜像位置m为2*c-i。
由于回文字符串的对称特性，此时p[i]的中心拓展长度应等于p[m]。
有几种特例情况，p[i]不等于p[m]：

如果p[m] + m的和大于r，则以m为中心扩展的范围超过当前c的中心扩展范围的右界。
此时p[i]无法保证等于p[m]。但是可以确保p[i]至少可以扩展到r，因此将p[i]更新为r-i。
如果i的位置等于r，则可扩展距离为0。
如果m的位置为原字符串的左边界，则此时将p[i]赋值为1是不正确的。
因为p[m]的计算是遇到了边界停止的，而p[i]则没有遇到边界，接下来对i位置从i+p[i]与i-p[i]开始继续进行中心扩展即可。

中心扩展

奇数项的回文字符串由中心扩展，只需要保证i+p[i]+1与i-p[i]-1（两个位置分别表示当前中心扩展的边缘再前进1）的字符相同，则可以继续向下扩展，将p[i]++。

c与r的更新

由于要保证i在r的范围之内，当从i出发的中心扩展范围大于c的中心扩展范围r，需要更新c与r。

时间复杂度

在进行扩展时，每次访问过的位置不会进入中心扩展算法。（比较从中心扩展的边缘开始，即i+p[i]+1与i-p[i]-1）
因此总的时间复杂度为O(n)。

Code

class Solution {
    int n;
    int[] p;
    String newString;
    public String longestPalindrome(String s) {
        n = s.length();
        StringBuffer sb = new StringBuffer();
        if(n == 0) {   //对字符串进行处理
            sb.append("^$");
        }
        else{
            sb.append("^");
            for(int i = 0; i < s.length(); i++){
                sb.append('#');
                sb.append(s.charAt(i));
            }
            sb.append("#$");
        }
        p = new int[sb.length()];
        newString = sb.toString();
        manacher();
        
        int c = 0;
        for(int i = 0; i < sb.length(); i++){
            if(p[i] > p[c]) c = i;
        }
        return s.substring( (c-p[c])/2, (c-p[c])/2+p[c] );
    }
    
    private void manacher(){
        int c = 0, r = 0;
        for(int i = 1; i < p.length - 1; i++){
            int m = 2 * c - i;
            if(i < r){  //当i在r的范围内时，p[i]的值与p[m]相等。
                p[i] = Math.min(r-i, p[m]); //当p[m] + i超过了r时(当前中心拓展边界)，p[i]至少可以取值到r-i
            }
            else{
                p[i] = 0; //当i等于r时，该位置拓展距离为0
            }
            
            while (newString.charAt(i+p[i]+1) == newString.charAt(i-p[i]-1)) {  //中心拓展算法，当两个位置相等时则可拓展距离+1
                p[i]++;
            }
            
            if(i + p[i] > r){   //当当前位置的右侧边界大于现有边界时，更新位置r
                c = i;
                r = i + p[i]; //新的右侧边界为新的中心+拓展长度p[i]
            }
        }
    }
}

Solution 2

getLength方法，计算每一个字符位置的回文长度。（将left填成i+1，right填成i则可以搜索偶数回文的长度。）
如果出现更长的回文，则根据返回的长度，和当前的i计算出字符串的范围。

Code

class Solution {
    public String longestPalindrome(String s) {
        int best = 0;
        int left = 0;
        int right = 0;
        for(int i = 0; i < s.length(); i++){
            int length = Math.max(getLength(s,i,i), getLength(s,i+1,i));
            if(best < length){
                left = i-((length-1)/2-1);
                right = i+(length/2);
                best = length;
            }
        }
        return s.substring(left,right);
    }
    
    private int getLength(String s, int left, int right){
        while(left >= 0 && right < s.length() && left < s.length()){
            if(s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            else break;
        }

        return right - left + 1;
    }
}

Posted 2022-04-23Updated 2022-04-23LeetCode / Medium / 复习a minute read (About 214 words)

43. Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

两个字符串的位数做乘法，每次计算进位。
当前位等于自身加上计算结果的个位（由于有之前的进位存在。），下一位等于计算结果的十位。

class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length();
        int n = num2.length();
        if( num1.equals("0") || num2.equals("0")){
            return "0";
        }
        int[] product = new int[m+n];
        
        char[] arr1 = num1.toCharArray();
        char[] arr2 = num2.toCharArray();
        
        for(int i = m-1; i >= 0; i--){
            for(int j = n-1; j >=0; j--){
                int sum = product[i+j+1] + (arr1[i] - '0') * (arr2[j] - '0');
                int curr = sum % 10;
                int carry = sum / 10;
            
                product[i+j] += carry;
                product[i+j+1] = curr;
            }
        }
        StringBuffer sb = new StringBuffer();
        for(int k = 0; k < m+n; k++ ){
            if(k == 0 && product[k] == 0 ) continue;
            sb.append(product[k]);
        }
        return sb.toString();
    }
}

Posted 2022-04-23Updated 2022-04-23LeetCode / Medium / 复习2 minutes read (About 246 words)

49. Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

利用JAVA中字符串会固定内存地址。（因此在进行字符串操作时是生成了新的对象。）
遍历每个单词，记录26个字母出现的次数，并映射到字符数组上。
将字符数组转换成字符串，生成一个新的字符串。

将字符串作为key放入map中，value储存原有单词。（字符串的内存地址固定，因此同样的字符串可以被搜索到。）

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ret = new ArrayList<>();
        HashMap<String, List<String>> map = new HashMap<>();
        
        for(String word : strs){
            char[] alphabet = new char[26];
            for(int j = 0; j < word.length(); j++){
                alphabet[word.charAt(j)-'a']++;
            }
            String s = new String(alphabet);
            List<String> str = map.getOrDefault(s, new ArrayList<String>());
            str.add(word);
            map.put(s, str);
        }
        for(String key : map.keySet()){
            ret.add(map.get(key));
        }
        return ret;   
    }
}

Posted 2022-04-21Updated 2022-04-21LeetCode / Mediuma minute read (About 219 words)

763. Partition Labels

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

将英文字母出现的首尾作为intervals看待。
根据字符创建数组并填入左右的index。
根据左侧index排序数组。

从左至右，如果intervals有交集，则合并。
否则在答案中添加当前interval的长度。

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[][] alphabet = new int[26][2];
        int head = s.charAt(0) - 'a';
        for(int i = 0; i < s.length(); i++){
            int index = s.charAt(i) - 'a';
            if(head != index && alphabet[index][0] == 0) alphabet[index][0] = i;
            alphabet[index][1] = i;
        }
        
        Arrays.sort(alphabet, (a,b) -> a[0] - b[0]);
        
        List<Integer> ans = new ArrayList();
        int[] hold = alphabet[0];
        for(int i = 1; i < alphabet.length; i++){
            if(alphabet[i][0] <= hold[1]){
                hold[1] = Math.max(hold[1], alphabet[i][1]);
            }
            else{
                ans.add(hold[1]-hold[0]+1);
                hold = alphabet[i];
            }
        }
        ans.add(hold[1]-hold[0]+1);
        return ans;
        
    }
}

Posted 2022-04-21Updated 2022-04-21LeetCode / Easy / 复习2 minutes read (About 299 words)

290. Word Pattern

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

先将s分割成数组。
如果words的长度和pattern的长度不同则返回false。
用长度为26的数组储存pattern的字符。
同时遍历words和pattern，将pattern的字符换算成数字作为index，将words[i]填入数组。
如果数组中已经有word存在，则检查新的word和数组内的word是否相等。
如果不相等，则返回false。

最后遍历数组，比对各个字符中对应的word是否相等，如果有相等的，则返回false。由于数组长度固定，因此这个操作的时间复杂度是O(1)。

class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");
        String[] alphabet = new String[26];
        
        if(words.length != pattern.length()){
            return false;
        }
        
        for(int i = 0; i < pattern.length(); i++){
            
            if( alphabet[pattern.charAt(i) - 'a'] != null){
                if(!alphabet[pattern.charAt(i) - 'a'].equals(words[i])){
                    return false;
                }
            }
            else{
                alphabet[pattern.charAt(i) - 'a']  = words[i];
            }
        }
        
        for(int i = 0; i < alphabet.length; i++){
            for(int j = i+1; j < alphabet.length; j++){
                if(alphabet[i] == null || alphabet[j] == null){
                    continue;
                }
                if(alphabet[i].equals(alphabet[j])){
                    return false;
                }
            }
        }
        
        return true;
    }
}

Posted 2022-04-21Updated 2022-04-20LeetCode / Easya minute read (About 159 words)

415. Add Strings

Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.

You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.

按照正常加法计算方法即可。
先将指针设置在两个String的末尾。
每次计算位置上加和的结果。
最后需要将字符串翻转过来。

class Solution {
    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int carry = 0;
        
        StringBuffer ans = new StringBuffer();
        
        while( i >= 0 || j >= 0 || carry > 0){
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + carry;
            
            ans.append(result % 10);
            carry = result / 10;
            
            i--;
            j--;
        }
        ans.reverse();
        return ans.toString();
    }
}

Posted 2022-04-21Updated 2022-05-04LeetCode / Easy / 复习a minute read (About 210 words)

409. Longest Palindrome

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, “Aa” is not considered a palindrome here.

回文字符串除了中心一个元素，其他的字符必须成对出现。因此可以直接统计字符串里有几组成对的字符。

用数组记录字符出现的次数。
如果数组中某个字符出现了两次，则可以将其归零。然后可以组成的最长回文数字加2。
如果字符串还剩下其他字符未选择，则最长回文数可以加一。

class Solution {
    public int longestPalindrome(String s) {
        int[] alphabet = new int['z' - 'A' + 1];
        int count = 0;
        int total = s.length();
        
        for(int i = 0; i < s.length(); i++){
            int index = s.charAt(i) - 'A';
            alphabet[index]+=1;
            if( alphabet[index] == 2 ){
                total -= 2;
                count += 2;
                alphabet[index] = 0;
            }
        }
        
        if(total != 0){
            count++;
        }

        return count;
    }
}

Posted 2022-04-20Updated 2022-04-20LeetCode / Medium / 复习2 minutes read (About 307 words)

438. Find All Anagrams in a String

Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

滑动窗口。采用两个数组分别计算两个字符串中字符出现的数量。

滑动窗口时，维护数组中字符串中字符出现的次数。
循环，判断两个字符串是否相等，如果相等，则将当前的左指针添加进答案。
移动窗口的左右指针，在数组中减少前一项出现的次数，增加后一项出现的次数。

通过维护一个表示两个字符串中字符差值的数组，可以将算法优化算法，而不必进行两个数组的比较。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {        
        List<Integer> ans = new ArrayList();
        if(p.length()>s.length()){
            return ans;
        }
        
        int[] alphabet = new int[26];
        int[] window = new int[26];
        
        for(int i = 0; i < p.length(); i++){
            alphabet[p.charAt(i) - 'a']++;
            window[s.charAt(i) - 'a']++;
        }
        
        int i = 0;
        int j = p.length();
        
        while(j < s.length()){
            if(Arrays.equals(alphabet, window)){
                ans.add(i);
            }
            window[s.charAt(i) - 'a']--;
            window[s.charAt(j) - 'a']++;
            i++;
            j++;
        }
        
        if(Arrays.equals(alphabet, window)){
            ans.add(i);
        }
        
        return ans;
        
    }
}

Posted 2022-04-19Updated 2022-05-04LeetCode / Medium / 复习2 minutes read (About 334 words)

844. Backspace String Compare

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

辅助方法getNextValid，返回下一个有效值。
将两个指针分别设置在两个字符串的尾部。
当两指针有一个大于0时，进行循环。
每次都搜索两个指针的下一个有效值。
如果两个指针上的字符不同则返回false。

最后返回两个指针的停留位置是否相同。

注意：
如果有一个字符串指针先更新到0以下，另一个指针仍有可能更新到一个“#”字符位置。
此时最后的结应该是两个空字符串。
因此需要继续循环一次，得出其是否会归到零以下。如果此时归零则两者的指针位置仍然相等。

因此即使getNextValid返回的下一个值为负数也应该保留其数值。

class Solution {
    public boolean backspaceCompare(String s, String t) {
        int i = s.length()-1;
        int j = t.length()-1;

        while(i >= 0 || j >= 0){
            i = getNextValid(s, i);
            j = getNextValid(t, j);
            if( i >= 0 && j >= 0 && s.charAt(i) != t.charAt(j)){    
                return false;
            }
            i--;
            j--;
        }
        return (i == j);
    }
    
    private int getNextValid(String s, int start){
        int i = start;
        int count = 0;
        while(i >= 0 && (s.charAt(i) == '#' || count != 0)){
            if(s.charAt(i) == '#'){
                count++;
            }
            else{
                count--;
            }
            i--;
        }
        return i;
    }
}

Posted 2022-04-13Updated 2022-04-23LeetCode / Medium / 复习a minute read (About 224 words)

784. Letter Case Permutation

答案
Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. Return the output in any order.

当前字符如果为数字，则直接添加并递归。（将字符隐式转换为整数判断是否为数字，可提升速度。）
当前字符如果为字母，则大小写分别添加到递归。（类似于回溯。）
当字符串长度与搜寻字符串相等时，添加到列表。

class Solution {
    List<String> ans;
    String _s;
    public List<String> letterCasePermutation(String s) {
        ans = new ArrayList();
        _s = s;
        
        backTrack(new StringBuilder(),0);
        return ans;
        
    }
    
    private void backTrack(StringBuilder sb, int i){
        if(i == _s.length()){
            ans.add(sb.toString());
            return;
        }
        char curr = _s.charAt(i);
        if ( isNums(curr) ){
            sb.append(curr);
            backTrack(sb, i+1);
        }
        else{
            StringBuilder sb2 = new StringBuilder(sb);
            sb.append(Character.toLowerCase(curr));
            backTrack(sb, i+1);
            sb2.append(Character.toUpperCase(curr));
            backTrack(sb2, i+1);
        }
    }
    
    private boolean isNums(char c){
        if ( (int)c >= (int)'0' && (int)c <= (int)'9' ){
            return true;
        }
        return false;
    }
}

Posted 2022-04-07Updated 2022-04-20LeetCode / Medium2 minutes read (About 235 words)

567. Permutation in String

问题
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1’s permutations is the substring of s2.

将要查找的组合加入数组，数值为字符出现的次数。
滑动窗口，入窗口对应的元素数值-1，出窗口对应的元素数值+1。
每次移动窗口都检验一次数组的数值是否全部为0，如果是真，则返回真。
小技巧：直接用数组来记录字符出现的次数，用字符减去与’a’的差作为下标。

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()){
            return false;
        }
        
        int[] dic = new int[26];
        for (int i = 0; i < s1.length(); i++){
            dic[s1.charAt(i)-'a']++;
            dic[s2.charAt(i)-'a']--;
        }
 
        int i = 0;
        int j = s1.length();
        
        while( j < s2.length() ){
            if ( allZero(dic) ){
                return true;
            }
            dic[s2.charAt(i)-'a']++;
            dic[s2.charAt(j)-'a']--;
            i++;
            j++;
        }
        return allZero(dic);
    }
    
    private boolean allZero(int[] dic){
        for (int num : dic){
            if ( num != 0 ){
                return false;
            }
        }
        return true;
    }
}

Posted 2022-04-07Updated 2022-06-10LeetCode / Medium / 复习2 minutes read (About 355 words)

3. Longest Substring Without Repeating Characters

Question

Given a string s, find the length of the longest substring without repeating characters.

Solution 1

滑动窗口加数组统计。
用一个数组bin[]记录各个字符的访问情况。（数组尺寸由字符串的总数决定）

当指针j第一次遍历到一个字符时，如果该字符对应的位置为0，则将其设置为1。
否则对前面的i指针进行遍历，并将i经过的位置重新设置为0。如果i的字符与当前j字符相等，则将bin[index]设置为0，计算当前的长度j-i并更新最大值best。

Code

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int best = 0, i = 0, j = 0;
        char[] word = s.toCharArray();
        int[] bin = new int[128];
        while(j < s.length()){
            int index = word[j] - ' ';
            if(bin[index] == 0){
                bin[index] = 1;
                j++;
            }
            else{
                while(i < j){
                    int temp = word[i] - ' ';
                    if(temp == index && bin[index] == 1){
                        bin[index] = 0;
                        best = Math.max(best, j - i);
                        i++;
                        break;
                    }
                    bin[temp] = 0;
                    i++;
                }
            }
            best = Math.max(best, j - i);
        }
        return best;
    }
}

Solution 2

滑动窗口，哈希表记录访问过的字符的元素。
如果重复，则放弃前一个重复的字符，更新左指针。
注意：只有在新指针大于现有指针时才更新！

Code

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int best = 0;
        int i = 0;
        int j = 0;
        
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        
        while ( j < s.length() ){
            char curChar = s.charAt(j);
            if ( !map.containsKey(curChar) ){
                map.put( curChar, j );
            }
            else{
                if ( map.get(curChar) + 1 > i){
                    i = map.get(curChar) + 1;
                }

                map.put( curChar, j );
            }
            
            if ((j - i + 1) > best){
                best = (j - i + 1);
            }
            j++;
        }
        return best;
    }
}

Posted 2022-04-07Updated 2022-04-20LeetCode / Easy / 复习a minute read (About 144 words)

680. Valid Palindrome II

问题
Given a string s, return true if the s can be palindrome after deleting at most one character from it.

双指针，字符串两边对比。
如果两边字符不相等，则更新两边指针，并分别传入辅助方法再次对比。
两个结果有一个是true则返回true。

class Solution {
    public boolean validPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        
        while (left < right){
            if (s.charAt(left) == s.charAt(right) ){
                left++;
                right--;
            }
            else{
                return ( checkPalindrome(s, left+1, right) || checkPalindrome(s, left, right-1));
            }
        }
        return true;
    }
    private boolean checkPalindrome(String s, int left, int right){
        while (left < right){
            if (s.charAt(left)==s.charAt(right)){
                left++;
                right--;
            }
            else{
                return false;
            }
        }
        return true;
    }    
}

Question

Solution

预处理

Manacher算法

中心扩展

c与r的更新

时间复杂度

Code

Solution 2

Code

Question

Solution 1

Code

Solution 2

Code

Recents

Archives

Links