Jiaming Zhang's Blog
0%

算法-字符串

发表于 更新于 分类于

字符串相关算法

求一个字符串中，最长无重复字符子串长度

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
public int lengthOfLongestSubstring(String s) {
       if (s == null || s.equals("")) {
           return 0;
       }
       char[] str = s.toCharArray();
       // 记录每个字符最后一次出现的位置
       int[] map = new int[256];
       for (int i = 0; i < 256; i++) {
           map[i] = -1;
       }
       int longestLength = 1;
       int pre = 1;
       map[str[0]] = 0;
       int N = str.length;
       for (int i = 1; i < N; i++) {
           // 假设后面的字符都不重复的最大值，还小于以求的最大值，则后面的位置不会出现最大值
           if (pre + N - i < longestLength) {
               break;
           }
           pre = Math.min(pre + 1, i - map[str[i]]);
           longestLength = Math.max(longestLength, pre);
           map[str[i]] = i;
       }
       return longestLength;
   }

只由小写字母（a~z）组成的一批字符串，都放在字符类型的数组String[] arr中，如果其中某两个字符串所含有的字符种类完全一样 就将两个字符串算作一类，比如baacbba和bac就算作一类，返回arr中有多少类

1
2
3
4
5
6
7
8
9
10
11
12
13
public int stringTypes(String[] arr) {
       HashSet<Integer> hashSet = new HashSet<>();
       for (String s : arr) {
           // 将字符串的字符映射到32位字节数组中，只用到低26位
           int type = 0;
           char[] chars = s.toCharArray();
           for (char c : chars) {
               type |= (1 << (c - 'a'));
           }
           hashSet.add(type);
       }
       return hashSet.size();
   }

假设所有字符都是小写字母，大字符串是str，arr是去重的单词表, 每个单词都不是空字符串且可以使用任意次。使用arr中的单词有多少种拼接str的方式，返回方法数

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
public class Solution {
    public int wordBreak(String str, String[] arr) {
        if (str == null || str.equals("") || arr == null || arr.length == 0) {
            return 0;
        }
        Map<Integer, Integer> cache = new HashMap<>();
        Set<String> set = new HashSet<>(Arrays.asList(arr));
        return splitWord(0, str, set, cache);
    }

    private int splitWord(int start, String str, Set<String> set, Map<Integer, Integer> cache) {
        if (cache.containsKey(start)) {
            return cache.get(start);
        }
        int N = str.length();
        if (start == N) {
            return 1;
        }
        int count = 0;
        StringBuilder prefix = new StringBuilder();
        for (int i = start; i < N; i++) {
            prefix.append(str.charAt(i));
            if (!set.contains(prefix.toString())) {
                continue;
            }
            count += splitWord(i+1, str, set, cache);
        }
        cache.put(start, count);
        return count;
    }
}