字符串篇六

字符串匹配

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

解法一：

  • 我刚一见到这个题解的时候，脑子里蹦出了插入排序的那个代码，虽然只是一个简单题，但是这个题细节方面写的也是一个细节怪的写法，就是这句i <= n - m;一懵还不理解，意思就是如果n - m个字符还没能匹配的上的话，那就没了呀 ……
  • 整体的时间复杂度O((n - m)*m)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
	int strStr(String ss, String pp){
		int m = ss.length(), n = pp.length();
		if (n > m) return -1;
		//对于原串进行逐个遍历
		for (int i = 0; i <= m - n; i++) {
			int a = 0, b = i;
			//匹配串遍历
			while (a < n && ss.charAt(b) == pp.charAt(a)){
				a++;
				b++;
			}
			if (a == n) return i;
		}
		return -1;
	}
}

解法二：

  • KMP算法
  • 时间复杂度O(m + n)

这算法真奇怪一个简单的题目，使用这种算法感觉理解起来立马难度增加了一个档次，真的很难懂呀，先背过，以后再慢慢说吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
	public static int strStr(String ss, String pp) {
		int n = ss.length(), m = pp.length();
		ss = " " + ss;
		pp = " " + pp;
		//要对于匹配串进行预处理
		int[] next = new int[m + 1];
		char[] s = ss.toCharArray(), p = pp.toCharArray();
		for (int i = 2, j = 0; i <= m; i++){
			//如果两个字符不相等，就逐个向着下标为1（因为填补过" "）的位置移动
			while (j > 0 && p[i] != p[j + 1]) j = next[j];
			//如果两个字符相等，两个指针都向前移动
			if (p[i] == p[j + 1]) j++;
			next[i] = j;
		}
		for (int i = 1, j = 0; i <= n; i++){
			while (j > 0 && s[i] != p[j + 1]) j = next[j];
			if (s[i] == p[j + 1]) j++;
            //这里的j和匹配串进行比较的返回的是第一个匹配的字符串的位置
			if (j == m) return i - m;
		}
		return -1;
	}
}

686. 重复叠加字符串匹配 - 力扣（LeetCode）

方法一：暴力解决

  • 感觉暴力的解法还是比较容易去理解的，看了几遍基本上一下就能写出来的那一种。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.HashSet;

class Solution {
    public int repeatedStringMatch(String a, String b) {
        int m = a.length(), n = b.length();
        //首尾各个添加一个
        if (!check(a, b)) return -1;
        int i = n / m + 2;
        String repeat = a.repeat(i);
        if (!repeat.contains(b)) return -1;
        for (int j = i - 1; j >= 0; j--){
            if (!a.repeat(j).contains(b)) return j + 1;
        }
        return -1;
    }
    boolean check(String a, String b){
        Set<Character> set = new HashSet<>();
        for (char c : a.toCharArray()) set.add(c);
        for (char c : b.toCharArray()){
            if (!set.contains(c)) return false;
        }
        return true;
    }
}

方法二：KMP算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int repeatedStringMatch(String a, String b) {
        StringBuilder bs = new StringBuilder();
        int ret = 0;
        while (bs.length() < b.length()){
            ret++;
            bs.append(a);
        }
        //这里再加一次我的理解是为了防止bs的长度恰好和b的长度相等，但是又不能完全匹配
        bs.append(a);
        int idx = Strstr(bs.toString(), b);
        if (idx == -1) return -1;
        return idx + b.length() <= a.length()*ret ? ret : ret + 1;
    }
    int Strstr(String ss, String pp){
        if (pp.isEmpty()) return 0;
        int m = ss.length(), n = pp.length();
        //对于匹配串进行预处理
        int[] next = new int[n + 1];
        //这里一定是" " + ss(空字符串+字符串)
        ss = " " + ss;
        pp = " " + pp;
        //ss:String原串  p : pattern匹配串
        char[] s = ss.toCharArray(), p = pp.toCharArray();
        //i从2开始，因为kmp的next数组的构造都是从1开始的，而下标1（即p[0]）没有前缀，next[1] = 0
        for (int i = 2, j = 0; i <= n; i++) {
            //如果两个指针所指向的字符不同，j就一直向前移动，一直移动到下标为1（就是第一个字符）的位置
            //这里j = next[j]我对于这个东西的理解是next[j]实际上就相当于j下标的前一位
            while (j > 0 && p[i] != p[j + 1]) j = next[j];
            //如果两个字符相等，两个指针一块移动
            if (p[i] == p[j + 1]) j++;
            next[i] = j;
        }
        for (int i = 1, j = 0; i <= m; i++){
            while (j > 0 && s[i] != p[j + 1]) j = next[j];
            if (s[i] == p[j + 1]) j++;
            if (j == n) return i - n;
        }
        return -1;
    }
}

方法三：时间复杂度极高的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int repeatedStringMatch(String a, String b) {
        StringBuilder bs = new StringBuilder();
        int ret = 0;
        while (bs.length() < b.length()){
            bs.append(a);
            ret++;
        }
        //想要完全匹配，至少bs的长度得大于b的长度，等于都不行
        bs.append(a);
        int idx = strStr(bs.toString(), b);
        if (idx == -1) return -1;
        //因为bs在最后多加了一次，所以不能使用bs
//        return idx + b.length() < bs.length() ? ret : ret + 1;
        return idx + b.length() <= a.length()*ret ? ret : ret + 1;
    }

    int strStr(String ss, String pp){
        int m = ss.length(), n = pp.length();
        if (n > m) return -1;
        //对于原串进行逐个遍历
        for (int i = 0; i <= m - n; i++) {
            int a = 0, b = i;
            //匹配串遍历
            while (a < n && ss.charAt(b) == pp.charAt(a)){
                a++;
                b++;
            }
            if (a == n) return i;
        }
        return -1;
    }
}

459. 重复的子字符串 - 力扣（LeetCode）

1
2
3
4
5
6
7
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String str = s + s;
        //破坏首和尾
        return str.substring(1, str.length() - 1).contains(s);
    }
}

214. 最短回文串 - 力扣（LeetCode）

  • s.substring(a, b)两个参数（左闭右开）
1
2
3
4
var str="abcdefghijklmn";
var res=str.substring(2,6);
 console.log(res);
结果res为："cdef"
  • s.substring(a)一个参数（闭区间）
1
2
3
4
var str="abcdefghijklmn";
var res=str.substring(3);
console.log(res);
结果res为："defghijklmn"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
	public String shortestPalindrome(String s) {
		int n = s.length();
		var next = new int[n + 1];
		s = " " + s;
		var c = s.toCharArray();
		for (int i = 2, j = 0; i <= n; i++) {
			//这里的j > 0，是因为next数组的构建是从1开始的
			while (j > 0 && c[i] != c[j + 1]) j = next[j];
			if (c[i] == c[j + 1]) j++;
			next[i] = j;
		}
		int len = 0;
		//从0到n是因为s = " " + s，这里的逆序串相当于原串，正序串相当于匹配串，它的极限就是一个正序加上一个逆序刚好凑成一个回文串
		for (int i = n; i > 0; i--) {
			while (len > 0 && c[len + 1] != c[i]) len = next[len];
			if (c[len + 1] == c[i]) len++;
		}
		String x = (len == n ? "" : s.substring(len + 1));
		StringBuilder res = new StringBuilder(x).reverse();
		res.append(s.substring(1));
		return res.toString();
	}
}

字符串变换

482. 密钥格式化 - 力扣（LeetCode）

这个题目对于某些细节方面的处理实在是我没有想得到的，还有就是ans.deleteCharAt(ans.length() - 1);这一句我没有想过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
	public String licenseKeyFormatting(String s, int k) {
		StringBuilder ret = new StringBuilder();
		int count = 0;
		for (int i = s.length() - 1; i >= 0 ; i--) {
			if (s.charAt(i) != '-'){
				count++;
				ret.append(Character.toUpperCase(s.charAt(i)));
				if (count % k == 0) ret.append('-');
			}
		}
		if (ret.length() > 0 && ret.charAt(ret.length() - 1) == '-') ret.deleteCharAt(ret.length() - 1);
		return ret.reverse().toString();
	}
}

6. Z 字形变换 - 力扣（LeetCode）

方法一：

这种方法确实写起来很简单，但是真的很难去想的到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public String convert(String s, int numRows) {
        int n = s.length();
        if(numRows == 1 || numRows >= n) return s;
        List<StringBuilder> lists = new ArrayList<>();
        for(int i = 0; i < numRows; i++) lists.add(new StringBuilder());
        int i = 0, flag = -1;
        for(char c : s.toCharArray()){
            lists.get(i).append(c);
            if(i == 0 || i == numRows - 1) flag *= -1;
            i += flag;
        }
        StringBuilder bs = new StringBuilder();
        for(int a = 0; a < lists.size(); a++) bs.append(lists.get(a));
        return bs.toString();
    }
}

方法二：模拟

构造一个x行y列的一个二维字符数组，将S中的字符逐个添加到字符数组中去，这个二维数组的行数就是numRows的值，二维数组的列数需要通过它的周期性变化进行计算

  • 通过numRows可以计算得出一整个周期的字符数还有一整个周期的列数
  • 一个周期有多少个字符？ t = numRows + numRows - 2个字符
  • 一个周期有多少列？ 1 + numRows - 2列也就是 numRows - 1列
  • 通过字符串总字符的个数以及一个周期字符数可以得出有多少个周期（上取整）总周期数为(n + t - 1)/t

通过总的周期数乘上每个周期的列数得出了二维数组的总列数

  • 所以得出这个字符需要总的列数为：[(n + t - 1)/t ] *(numRows - 1)

上取整操作还是有一些技巧在里面的就比如a/b进行上取整操作就是(a + b - 1)/b因为a / b加的这个值肯定是小于1的（通过分子给足了b的面子，你最多就是加上一个1假如就取得一个极限值a = 1那么就是1/b进行上取整）这么理解真的通了

上述步奏都想通了昨天做的时候，字符周期性变化没有想通（看了答案想通了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public String convert(String s, int numRows) {
        int n = s.length();
        if(numRows == 1 || numRows > n) return s;
        int t = numRows*2 - 2;
        int c = (n + t - 1)/t *(numRows - 1);
        char[][] v  = new char[numRows][c];
        int x = 0, y = 0;
        for(int i = 0; i < n; i++){
            v[x][y] = s.charAt(i);
            if(i % t < numRows - 1) x++;
            else{
                x--;
                y++;
            }
        }
        StringBuilder bs = new StringBuilder();
        for(char[] d : v){
            for(char k : d){
                if(k != 0) bs.append(k);
            }
        }
        return bs.toString();
    }
}

tips总的来说这几天的这个子序列真的让我受益匪浅，真的感觉了解了许多，前几天的那两个动态规划，这两天的KMP这几个这几天真的弄得我很难理解但是我都硬啃下来了。

算法
#leetcode
字符串篇六
http://example.com/2024/04/09/str6/
作者
nianjx
发布于
2024年4月9日
许可协议