关于leetcode:leetcode-字符串

45次阅读

共计 6524 个字符,预计需要花费 17 分钟才能阅读完成。

@TOC

字符串循环移位蕴含

编程之美 3.1

s1 = AABCD, s2 = CDAA
Return : true

题解: 给定两个字符串 s1 和 s2,要求断定 s2 是否可能被 s1 做循环移位失去的字符串蕴含。
s1 进行循环移位的后果是 s1s1 的子字符串,因而只有判断 s2 是否是 s1s1 的子字符串即可。

字符串循环移位

编程之美 2.17

s = "abcd123" k = 3
Return "123abcd"

题解:
将字符串向右循环挪动 k 位。
将 abcd123 中的 abcd 和 123 独自翻转,失去 dcba321,而后对整个字符串进行翻转,失去 123abcd。

字符串中单词的翻转

程序员代码面试指南

s = "I am a student"
Return "student a am I"

题解:
将每个单词翻转,而后将整个字符串翻转。


242. 无效的字母异位词 * (简略)

给定两个字符串 s 和 t,编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输出: s = "anagram", t = "nagaram"
输入: true

示例 2:

输出: s = "rat", t = "car"
输入: false

阐明:
你能够假如字符串只蕴含小写字母。
进阶:
如果输出字符串蕴含 unicode 字符怎么办?你是否调整你的解法来应答这种状况?

题解:
1. 转换为数组再排序
将两个字符串排序,字母异位词排序后截然不同。
首先判断长度是否相等,不相等间接返回 false;

class Solution {public boolean isAnagram(String s, String t) {
    // 长度不相等,立刻返回 false
    if (s.length() != t.length()) {return false;}
    // 字符串转化为数组
    char[] str1 = s.toCharArray();
    char[] str2 = t.toCharArray();
    // 数组排序
    Arrays.sort(str1);
    Arrays.sort(str2);
    // 数组比拟
    return Arrays.equals(str1, str2);
    }
}

工夫复杂度 O(nlogn)
空间复杂度 O(1): 空间取决于排序实现,如果应用 heapsort,通常须要 O(1) 辅助空间。留神,在 Java 中,toCharArray() 制作了一个字符串的拷贝,所以它破费 O(n) 额定的空间,然而咱们疏忽了这一复杂性剖析,因为:这依赖于语言的细节。这取决于函数的设计形式。例如,能够将函数参数类型更改为 char[]。

2. 桶计数

// 字母桶计数 ver1:
// 若两个字符串长度不等,立刻返回 false
// 先对 s 中字符计数
// 对 t 中字符计数,t 中相应字符计数减 1,若某个字母计数小于 0,立刻返回 false
class Solution {public boolean isAnagram(String s, String t) {int[] table = new int[26];
        if (s.length() != t.length()){return false;}
        // s 中的字符计数
        for (int i= 0; i<s.length(); i++){table[s.charAt(i)-'a']++;   
        }
        
        // s 计数根底上,t 中相应字符计数减 1
        for (int i = 0; i<t.length(); i++){table[t.charAt(i) - 'a']--;
            if (table[t.charAt(i) - 'a'] < 0)   // 若某一个字符计数小于 0 时,立刻返回 false
                return false;
        }
        return true;
    }
}
// 字母桶计数 ver2:
// 若两个字符串长度不等,立刻返回 false
// 先对 s 中字符计数
// 查看字母表是否每个字符计数为 0,不是返回 false
class Solution {public boolean isAnagram(String s, String t) {int[] table = new int[26];
        if (s.length() != t.length()){return false;}
        // s 中的字符计数
        for (int i= 0; i<s.length(); i++){table[s.charAt(i)-'a']++;   
            table[t.charAt(i)-'a']--;
        }
        
        // s 计数根底上,t 中相应字符计数减 1
        for (int i = 0; i<26; i++){if (table[i]!=0)
                return false;
        }
        return true;
    }
}

工夫复杂度 O(n)
空间复杂度 O(1)


409. 最长回文串

给定一个蕴含大写字母和小写字母的字符串,找到通过这些字母结构成的最长的回文串。
在结构过程中,请留神辨别大小写。比方 “Aa” 不能当做一个回文字符串。
留神:
假如字符串的长度不会超过 1010。

示例 1:

输出:
"abccccdd"
输入:
7

解释:
咱们能够结构的最长的回文串是 ”dccaccd”, 它的长度是 7。

题解:
对于回文字符串,最多只有一个字符的个数是 1 个,其余字符必为偶数个
用一个桶统计每个呈现的字符的个数。
某字母个数为偶数个,加上该字母个数
某字母个数为奇数个,加上该字母的个数再减 1
若后果长度小于原字符串长度:后果长度再加 1

class Solution {public int longestPalindrome(String s) {
        int res = 0;
        // 大写和小写字母之间有 6 个其余字符,因而数组大小:52+6
        int[] bucket = new int[58];
        
        for (int i = 0; i<s.length(); i++){bucket[s.charAt(i) - 'A'] ++; 
        }
        int flag = 0;
        for (int x: bucket){res += x - (x & 1);  // 取 x 的最大偶数个,若 x 为奇数,则减 1
        }
        // 若后果长度比 s 长度小,再加上一个字母的长度
        return res<s.length()? res+1: res;}
}

工夫复杂度 O(n)
空间复杂度 O(1)


5. 最长回文子串

给定一个字符串 s,找到 s 中最长的回文子串。你能够假如 s 的最大长度为 1000。

示例 1:

输出: "babad"
输入: "bab"
留神: "aba" 也是一个无效答案。

示例 2:

输出: "cbbd"
输入: "bb"
// 核心扩大
class Solution {public String longestPalindrome(String s) {if (s == null || s.length() < 2) {return s;}
        int max_len = 1;
        int start = 0;
        int n = s.length();
        for(int i = 0; i<n; i++){
            int left = i-1; 
            int right = i+1;
            while(left>=0 && s.charAt(left) == s.charAt(i)){left--;}
            while (right<n && s.charAt(right) == s.charAt(i)){right++;}
            while(left>=0 && right<n && s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            if (right-left-1 > max_len){
                max_len = right-left-1;
                start = left+1;
            }
        }
        return s.substring(start, start+max_len);
    }
}

工夫复杂度 O(n^2)
空间复杂度 O(1)


647. 回文子串

给定一个字符串,你的工作是计算这个字符串中有多少个回文子串。
具备不同开始地位或完结地位的子串,即便是由雷同的字符组成,也会被视作不同的子串。

示例 1:

输出:"abc"
输入:3
解释:三个回文子串: "a", "b", "c"

示例 2:

输出:"aaa"
输入:6
解释:6 个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提醒:
输出的字符串长度不会超过 1000。


205. 同构字符串

给定两个字符串 s 和 t,判断它们是否是同构的。
如果 s 中的字符能够被替换失去 t,那么这两个字符串是同构的。
所有呈现的字符都必须用另一个字符替换,同时保留字符的程序。两个字符不能映射到同一个字符上,但字符能够映射本人自身。

示例 1:

输出: s = "egg", t = "add"
输入: true

示例 2:

输出: s = "foo", t = "bar"
输入: false

示例 3:

输出: s = "paper", t = "title"
输入: true

阐明:
你能够假如 s 和 t 具备雷同的长度。

题解:
1. 两个哈希表
依据题意,s 惟一地映射到 t,且 t 惟一地映射到 s.

如 s = "foo", t = "bar" 不同构
o -> a
o -> r
o 映射到了两个字母
如 s = "ab", t = "cc" 不同构
a -> c
b -> c
c 被映射了两次
反过来由 t 映射到 s
c -> a 
c -> b
c 映射到了两个字母

因而须要验证 s->t 成立,且 t->s 成立

class Solution {public boolean isIsomorphic(String s, String t) {Map<Character, Character> map1 = new HashMap<>();  //s->t
        Map<Character, Character> map2 = new HashMap<>();  //t->s
        
        for (int i = 0; i < s.length(); i++){//map1 中不蕴含 s[i]的映射, map2 也不蕴含 t[i]的映射,则将 s[i]<->t[i] 退出映射表中
            if (!map1.containsKey(s.charAt(i)) && !map2.containsKey(t.charAt(i))){map1.put(s.charAt(i), t.charAt(i));
                map2.put(t.charAt(i), s.charAt(i));
            }
            else{// 若 map1 中存在 s[i]的映射,但 s[i]-/>t[i], 返回 false
                if (map1.containsKey(s.charAt(i)) && map1.get(s.charAt(i)) != t.charAt(i))
                    return false;
                // 若 map1 中存在 t[i]的映射,但 t[i]-/>t[i], 返回 false
                else if (map2.containsKey(t.charAt(i)) && map2.get(t.charAt(i))!= s.charAt(i))
                    return false;
            } 
        }
        return true;
    }
}

工夫复杂度 O(n)
空间复杂度 O(n)

2. 一个哈希表
s -> t 与 t -> s 两个方向分次进行

class Solution {public boolean isIsomorphic(String s, String t) {return help(s, t) && help(t, s);
    }
    
    public boolean help(String s, String t){Map<Character, Character> map = new HashMap<>();
        for (int i = 0; i< s.length(); i++){char ch1 = s.charAt(i);
            char ch2 = t.charAt(i);
            if (!map.containsKey(ch1)){map.put(ch1, ch2);
            }
            else if (map.get(ch1) != ch2)
                return false;
        }
        return true;
    }
}

工夫复杂度 O(n)
空间复杂度 O(n)


9. 回文数

判断一个整数是否是回文数。回文数是斧正序(从左向右)和倒序(从右向左)读都是一样的整数。

示例 1:

输出: 121
输入: true

示例 2:

输出: -121
输入: false
解释: 从左向右读, 为 -121。从右向左读, 为 121-。因而它不是一个回文数。

示例 3:

输出: 10
输入: false
解释: 从右向左读, 为 01。因而它不是一个回文数。

进阶:
你能不将整数转为字符串来解决这个问题吗?

题解:
1. 数字转化为字符串

2. 将整个数字翻转
回文数翻转后和原来的数相等。
翻转的形式:

revertedNum = revertedNum*10 + temp%10;
temp = temp/10;

class Solution {

public boolean isPalindrome(int x) {if (x<0 || ( x%10 == 0 && x!=0)){  // 留神边界条件
        return false;
    }
    int temp = x;
    int revertedNum = 0;
    while (temp > 0){
        revertedNum = revertedNum*10 + temp%10;
        temp = temp/10;
    }
    return x == revertedNum;
}

}

工夫复杂度 O(log10(n))
空间复杂度 O(1)


**3. 翻转一半的数 **
翻转了一半时:x < revertedNum
同时留神,当原数有奇数位数时,翻转后的数会多一位,只有再除以 10 而后比拟即可。最初留神边界条件。- 当 x 为正数时,不是回文数
- 当 x 非 0,但最初一位为 0 时,不是回文数

class Solution {

public boolean isPalindrome(int x) {if (x<0 || ( x%10 == 0 && x!=0)){  // 留神边界条件
        return false;
    }
    
    int revertedNum = 0;
    while (x > revertedNum){
        revertedNum = revertedNum*10 + x%10;
        x = x/10;
    }
    return x == revertedNum || x == revertedNum/10;
}

}

工夫复杂度 O(log10(n))
空间复杂度 O(1)

***

## 696. 计数二进制子串

> 给定一个字符串 s,计算具备雷同数量 0 和 1 的非空 (间断) 子字符串的数量,并且这些子字符串中的所有 0 和所有 1 都是组合在一起的。反复呈现的子串要计算它们呈现的次数。** 示例 1 :**

输出: “00110011”
输入: 6
解释: 有 6 个子串具备雷同数量的间断 1 和 0:“0011”,“01”,“1100”,“10”,“0011”和“01”。

> 请留神,一些反复呈现的子串要计算它们呈现的次数。另外,“00110011”不是无效的子串,因为所有的 0(和 1)没有组合在一起。** 示例 2 :**

输出: “10101”
输入: 4
解释: 有 4 个子串:“10”,“01”,“10”,“01”,它们具备雷同数量的间断 1 和 0。


** 留神:**
s.length 在 1 到 50,000 之间。s 只蕴含“0”或“1”字符。** 题解:**
**1. 按字符分组 **
将字符串 `s` 转换为 `arr` 数组示意字符串中雷同字符间断块的长度。例如,如果 s=“11000111000000”,则 arr=[2,3,3,6]。-  `'0' * k + '1' * k` 或 `'1' * k + '0' * k` 模式的每个二进制字符串,有 k 个子串。- 对于相邻的两个字符块,`arr[i-1]` 和 `arr[i]` 的子串个数为 `min(arr[i-1], arr[i])`

// 按字符分组
class Solution {

public int countBinarySubstrings(String s) {
    int res = 0;
    int n = s.length();
    if (n == 0 || n == 1){return res;}
    
    // 按字符分组,寄存到 arr 中
    int[] arr = new int[n];
    arr[0] = 1;
    int index = 0;
    for (int i = 1; i < s.length(); i++){if (s.charAt(i) == s.charAt(i-1)){arr[index]++; 
        }else{arr[++index] = 1;
        }
    }
    // 计算每个相邻字符块的字串个数
    for (int i = 1; i<n; i++){res += Math.min(arr[i], arr[i-1]);
    }
    return res;
}

}

工夫复杂度 O(n)
空间复杂度 O(n)

**2. 线性扫描 **
时时记录后果

class Solution {

 public int countBinarySubstrings(String s) {int n = 0, pre = 0, curr = 1, len = s.length()-1;
    for (int i = 0; i < len; ++i) {if (s.charAt(i) == s.charAt(i+1)) 
            curr++;
        else{
            pre = curr; 
            curr = 1;
        }               
        if (pre >= curr)
            ++n;
    }
   return n;
}

}

工夫复杂度 O(n)
空间复杂度 O(1)

正文完
 0