理论部分
- 用数组实现一个顺序的串结构。
- 为该串结构提供丰富的操作，比如插入子串、在指定位置移除给定长度的子串、在指定位置取子串、连接串、串匹配等。
代码实现
/**
* 插入子串、
* 在指定位置移除给定长度的子串、
* 在指定位置取子串、连接串、串匹配等。
*/
public class MString {
private char[] str;
private int length;
// 数组长度。
public int length(){
return length;
}
public MString(){
str = new char[10];
length = 0;
}
public MString(String s){
str = s.toCharArray();
length = s.length();
}
// 扩充数组
private void resize(int capacity){
if(capacity <= 0)
return;
char [] temp = new char[capacity];
for(int i = 0; i < length; i ++)
temp[i] = str[i];
str = temp;
}
public void append(String s){
insert(length, s);
}
public void insert(int index, String s){
if(str.length <= (s.length() + length))
resize((int)((s.length() + length)*1.5));
for(int i = length - 1, d = s.length(); i >= index; -- i)
str[i+d] = str[i];
for(int i = 0; i < s.length(); ++ i)
str[index ++] = s.charAt(i);
length += s.length();
}
// 指定位置移除给定长度的子串
public void remove(int index, int moveLen){
if(length == 0)
return;
for (int i = index; i < length - moveLen; ++ i)
str[i] = str[i + moveLen];
length -= moveLen;
}
// 获取指定位置的字符串
public String get(int start, int end){
char[] s = new char[end - start];
for(int i = 0, j = start; j < end; ++ j)
s[i] = str[j];
return new String(s);
}
// 连接两个字符串
public String contact(String s){
if(s.length() != 0)
append(s);
return new String(str);
}
// 串匹配，判断主串是否存在字符串
public boolean isInclude(String ms){
// 循环的次数
int num = length - ms.length() + 1;
for(int i = 0; i < num; i ++){
int j;
for(j = 0; j < ms.length(); j++){
if(ms.charAt(j) != str[i+j])
break;
}
if(j == ms.length())
return true;
}
return false;
}
public String toString(){
return new String(str);
}
}
练习部分
1. 无重复字符的最长子串
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例1
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例2
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例3
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
思路
1. 初始化一个长度为 128 的 boolean flag数组,用来记录最大重复子串的字符（利用到字符的ascii码作为数组的下标）。
2. 利用到滑动窗口的思想，外层循环 i 控制最大无重复子串的起始位置，嵌套循环 j=i+1 控制结束位置，如果 j 滑动时碰到 flag[j]=true（即表示最大重复子串已存在相同的字符）结束循环，更新最大重复子串的长度，如果 flag[j] = false（即最大重复子串不存在相同的字符），则 flag[j] = true,子串的长度 len++。
代码实现
class Solution {
public int lengthOfLongestSubstring(String s) {
boolean[] flag = new boolean[128];
int start, sublen = 0;
for(int i = 0; i < s.length(); i ++){
// 每一轮都重新初始化 flag[] 的值
for(int k = 0; k < flag.length; k++)
flag[k] = false;
flag[(int)(s.charAt(i))] = true; // i 起始字符
int len = 1;
for(int j = i+1; j < s.length(); j ++){
if(flag[(int)(s.charAt(j))])
break;
else{
len ++;
flag[(int)(s.charAt(j))] = true;
}
}
if(sublen < len){
sublen = len;
start = i;
}
}
return sublen;
}
}
2. 串联所有单词的子串
https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/
给定一个字符串s和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例1
输入：
s = "barfoothefoobarman",
words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。输出的顺序不重要, [9,0] 也是有效答案。
示例2
输入：
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
输出：[]
代码实现
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<>();
if(words.length == 0 || s.length() == 0)
return res;
int wordLen = words[0].length();
int strLen = s.length();
int wordsNum = words.length;
int allWordsLen = wordLen * words.length;
// 记录 worlds 对应的单词数
Map<String, Integer> map = new HashMap<>();
for(int i = 0; i < wordsNum; i ++)
map.put(words[i], map.getOrDefault(words[i], 0) + 1);
for(int i = 0; i < strLen - allWordsLen + 1; i ++){
Map<String, Integer> tmp_map = new HashMap<>();
for(int j = i; j < i + allWordsLen; j += wordLen){
String sub = s.substring(j, j + wordLen);
if(!map.containsKey(sub))
break;
else
tmp_map.put(sub, tmp_map.getOrDefault(sub, 0)+1);
}
// 判断 tmp_map 和 map 是否相同
if(tmp_map.equals(map))
res.add(i);
}
return res;
}
}
3. 替换子串得到平衡字符串
https://leetcode-cn.com/problems/replace-the-substring-for-balanced-string/
有一个只含有'Q', 'W', 'E','R'四种字符，且长度为 n的字符串。假如在该字符串中，这四个字符都恰好出现n/4次，那么它就是一个「平衡字符串」。
给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串s变成一个「平衡字符串」。你可以用和「待替换子串」长度相同的任何其他字符串来完成替换。
请返回待替换子串的最小可能长度。
如果原字符串自身就是一个平衡字符串，则返回 0。
示例1：
输入：s = "QWER"
输出：0
解释：s 已经是平衡的了。
示例2：
输入：s = "QQWE"
输出：1
解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。
示例3：
输入：s = "QQQW"
输出：2
解释：我们可以把前面的 "QQ" 替换成 "ER"。
示例4：
输入：s = "QQQQ"
输出：3
解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。
代码实现
class Solution {
public int balancedString(String s) {
Map<Character, Integer> map = new HashMap<>();
for(int i = 0;i < s.length(); i ++)
map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
int left = 0, right=0;
int res = s.length();
// 滑动窗口
while(right < s.length()){
map.put(s.charAt(right), map.get(s.charAt(right))-1);
right ++;
// 判断 q,w,e,r 单词是否超过 s.length()/4;
while(left < s.length() && check(map, s.length()/4)){
res = Math.min(res, right - left);
map.put(s.charAt(left), map.get(s.charAt(left))+1);
left ++;
}
}
return res;
}
// 检查
public boolean check(Map<Character, Integer> map, int num){
Set<Character> set = map.keySet();
for(Character c: set){
if(map.getOrDefault(c, 0) > num)
return false;
}
return true;
}
}
