wuxin0011`blog
wuxin0011
2024-01-12
目录

前缀树+滑动窗口解决子串问题

# 题外话

在力扣上解决问题有时候调试是很困难的，【ps:因为要开会员 ❤️】,一般都会在本地IDE中创建一个Java文件，class Name ，因为命名是一个问题，

比如复制链接https://leetcode.cn/problems/substring-with-concatenation-of-all-words/ 后缀为文件名，先复制过来 substring-with-concatenation-of-all-words，

然后一通修改横线为下划线，如果不遵循驼峰命名，然后IDE就给出很烦人的波浪线~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~,然后修改为SubstringWithConcatenationOfAllWords

…… ☕

毫无疑问这些操作是十分浪费时间的但是有不得不做，如果你以 A,B 或者序号命名也可以。作为一个XXXX,可以用代码解决的这些操作，就没比要用手了！

为此我单独写了一个工具类 【ps:暂时无法获取文字说明信息，因为是html格式，如果一一解析又浪费时间了感觉使用现有的库又没有必要☕】

package com.demo.TreeNode.Code01;


import java.io.File;
import java.io.FileOutputStream;

public class BuildLeetCodeName {

	public static void main(String[] args) {
		String url = "https://leetcode.cn/problems/substring-with-concatenation-of-all-words/";
		build(url)
	}

	public static String build(String url) {
		return build(url, true, "", "");
	}

	/**
	 * 
	 * @param url
	 * @param create
	 * @param pkgName
	 * @param rootDirName
	 * @return
	 */
	public static String build(String url, boolean create, String pkgName, String rootDirName) {
		//https://leetcode.cn/problems/print-words-vertically/description/
		url = url.replace("/description", "");
		url = url.replace("https://leetcode.cn/problems/", "");
		url = url.replace("https://leetcode.cn", "");
		StringBuilder sb = new StringBuilder();
		char[] cs = url.toCharArray();
		int n = cs.length;
		for (int i = 0; i < cs.length; i++) {
			char c = cs[i];
			if (c == '/') {
				continue;
			}
			if (i == 0) {
				c = toUpper(c);
			}
			if (c == '-' && i + 1 < n) {
				i++;
				c = toUpper(cs[i]);
			}
			sb.append(c);
		}
		String fileName = sb.toString();
		if (create) {
			createFile(fileName);
		}

		return fileName;
	}

	public static boolean isLower(char c) {
		return 'a' <= c && 'z' >= c;
	}

	public static char toUpper(char c) {
		if (!isLower(c))
			return c;
		return (char) (c - 'a' + 'A');
	}

	public static void createFile(String fileName) {
		createFile(fileName, "", "");
	}

	/**
	 * 创建文件
	 * 
	 * @param fileName    文件名
	 * @param packageName 包名 默认会创建在文件路径下
	 * @param rootName    根文件夹名 默认是 src
	 */

	public static void createFile(String fileName, String packageName, String rootName) {
		System.out.println(fileName + " create ... ");
		String className = fileName;
		// 获取包类信息
		if (null == packageName || packageName.length() == 0) {
			Package pkg = BuildLeetCodeName.class.getPackage();
			packageName = pkg.getName();
		}
        
        if (rootName == null || rootName.length() == 0) {
			rootName = "src";
		}
		StringBuilder sb = new StringBuilder();
        sb.append(rootName);
		sb.append(File.separatorChar);
		// 通过包类构建文件创建路径
		for (int i = 0; i < packageName.length(); i++) {
			if (packageName.charAt(i) == '.') {
				sb.append(File.separatorChar);
			} else {
				sb.append(packageName.charAt(i));
			}
		}
		sb.append(File.separatorChar);
		String path = sb.toString();
		File file = new File(path);

		if (!file.exists()) {
			file.mkdirs();
		}

		sb.append(fileName);
		if (!fileName.endsWith(".java")) {
			sb.append(".java");
		}
		fileName = sb.toString();
		file = new File(fileName);
		if (file.exists()) {
			System.out.println("create fail ! because " + className + " already exists! on" + fileName);
			return;
		}

		try {
			file.createNewFile();
			FileOutputStream fos = new FileOutputStream(file);

			StringBuilder info = new StringBuilder();

			// 写入文件内容
            if( packageName != null && packageName.length() != 0 ){
                info.append("package");
                info.append(" ");
                info.append(packageName);
                info.append(";");
            }
			for (int i = 0; i < 3; i++) {
				info.append("\n");
			}
			
			info.append("import java.util.*;");
			
			for (int i = 0; i < 3; i++) {
				info.append("\n");
			}

			info.append("public class "+className+" {\r\n"
					+ "	\r\n"
					+ "	\r\n"
					+ "	static class Solution {\r\n"
					+ "		\r\n"
					+ "	}\r\n"
					+ "\r\n"
					+ "	public static void main(String[] args) {\r\n"
					+ "		Solution solo = new Solution();\r\n"
					+ "	}\r\n"
					+ "\r\n"
					+ "}");

			fos.write(info.toString().getBytes());

			fos.flush();
			fos.close();
			System.out.println("create class success:" + className);
		} catch (Exception e) {
			e.printStackTrace();
		}

	}


}
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169

控制台打印成功信息

SubstringWithConcatenationOfAllWords create ... 
create class success:SubstringWithConcatenationOfAllWords
1
2

生成的文件

package com.demo.TreeNode.Code01;


import java.util.*;


public class SubstringWithConcatenationOfAllWords {
	
	
	static class Solution {
		
	}

	public static void main(String[] args) {
		Solution solo = new Solution();
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

可以看到生成文件包括一下内容

  • package 一般为当前运行包
  • 自动引入 java.util.*; 这个是允许的
  • 类名符合驼峰命名规范。
  • 自动创建 main 函数并创建调用对象Solution

你只需要在 Solution 中编写函数逻辑或者复制过来调试🍖

是不是简化操作了呢？

# 题目链接

串联所有子串 (opens new window)

# 思路

分析

  1. 根据题目可知words 中单词每个长度相等 从长度信息可以知道 这个想到滑动窗口
  2. 单词没说能不能重复，仅仅说每个单词只能使用一次这个很重要 这个联想到前缀树
  3. 每个索引位置单词只能必须使用且只能使用一次

一般来说前缀树构建是这样的

static class TrieNode {
    TrieNode[] nexts;
    boolean isEnd; // 是否为结束位置

    public TrieNode() {
        this.nexts = new TrieNode[26];
        this.isEnd = false;
    }
}


// 辅助函数构建前缀树
public static void buildTrieNode(TrieNode root, String[] words) {
    for (String s : words) {
        TrieNode cur = root;
        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            if (cur.nexts[idx] == null) {
                cur.nexts[idx] = new TrieNode();
            }
            cur = cur.nexts[idx];
        }
        cur.isEnd = true;
    }
}
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

这样肯定不通过，比如

String[] words = { "ab", "ca"}; 
String s = "abab";
1
2

这个测试案例应该是[]

但是因为不知道有多少个ab造成abab 也能通过

作为计数器，怎么能少了 哈希函数呢 ？map.put(cur, cur.val);

此时前缀树构造成下面所示

static class TrieNode {
    TrieNode[] nexts;
    int val; // 表示多少个
    boolean isEnd; // 是否为结束位置

    public TrieNode() {
        this.nexts = new TrieNode[26];
        this.isEnd = false;
        this.val = 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11

此外不能对前缀树做任何修改【修改后面就无法判断了!】

因此需要两个哈希函数辅助来记住该窗口中单词使用数量

  • 一个用来记录初始状态信息
  • 一个用来当前使用信息

此时使用判断情况应该是

  • 又没有路径
  • 辅助哈希函数和初始函数大小所有内容必须全等
    • size
    • cnt

需注意 由于map 中存放value是int的包装类型，也就是说 在对象相等范围为[-128,127]，所以应该使用equlas方法（ps:因为这里我被坑了提交了好几次不通过😅），这么简单东西都能忘记。

因此解答如下

package com.demo.TreeNode.Code01;

import java.util.*;

public class SubstringWithConcatenationOfAllWords {

	static class Solution {
        
		static class TrieNode {
			TrieNode[] nexts;
			int val; // 该位置结束有多少个
			boolean isEnd; // 是否为结束位置

			public TrieNode() {
				this.nexts = new TrieNode[26];
				this.val = 0;
				this.isEnd = false;
			}
		}

		/**
		 * 构建前缀树
		 * 
		 * @param root  树
		 * @param words 路径单词
		 */
		public static void buildTrieNode(TrieNode root, String[] words, Map<TrieNode, Integer> map) {
			for (String s : words) {
				TrieNode cur = root;
				for (int i = 0; i < s.length(); i++) {
					int idx = s.charAt(i) - 'a';
					if (cur.nexts[idx] == null) {
						cur.nexts[idx] = new TrieNode();
					}
					cur = cur.nexts[idx];
				}
				cur.isEnd = true;
				cur.val++;
				map.put(cur, cur.val);
			}
		}

		/**
		 * 检查
		 * 
		 * @param root 前缀树
		 * @param s    当前单词
		 * @param st   检查开始索引
		 * @param ed   结束索引
		 * @param step 每次移动索引
		 * @return boolean
		 */
		public static boolean check(TrieNode root, String s, int st, int ed, int step, Map<TrieNode, Integer> map) {
			Map<TrieNode, Integer> helpMap = new HashMap<>();
			for (int i = st; i < ed; i += step) {
				int cnt = 0;
				TrieNode cur = root;
				while (cnt != step) {
					int index = s.charAt(i + cnt) - 'a';
					if (cur.nexts[index] == null) {
						return false;
					}
					cur = cur.nexts[index];
					cnt++;
				}
				if (!cur.isEnd)
					return false;
				int val = helpMap.getOrDefault(cur, 0) + 1;
				if (val > map.get(cur))
					return false;
				helpMap.put(cur, val);
			}

			if (helpMap.size() != map.size()) {
				return false;
			}

			for (Map.Entry<TrieNode, Integer> m : map.entrySet()) {
				if (!helpMap.containsKey(m.getKey())) {
					return false;
				}

				// 艹 这里又忘记了 Integer > 127 时候比较要使用对象比较
				if (!m.getValue().equals(helpMap.get(m.getKey()))) {
					return false;
				}
			}

			return true;
		}

		public List<Integer> findSubstring(String s, String[] words) {

			List<Integer> ans = new ArrayList<>();
			int n = s.length();
			int m = words.length;
			int step = words[0].length();
			int width = m * step;
			// 如果 words 中所有单词构成字串数量还不够 说明需要退出
			if (width > n)
				return ans;
			TrieNode root = new TrieNode();
			Map<TrieNode, Integer> map = new HashMap<>();

			// 构建前缀树
			buildTrieNode(root, words, map);
			for (int i = 0; i < n - width + 1; i++) {
				if (check(root, s, i, i + width, step, map)) {
					ans.add(i);
				}
			}
			return ans;
		}

	}

	public static void main(String[] args) {
		Solution sub = new Solution();
		String[] words = { "foo", "bar" }; 
		String s = "barfoothefoobarman";

		System.out.println(sub.findSubstring(s, words));
		String s1 = "barfoofoobarthefoobarman";

		String[] words1 = { "bar", "foo", "the" }; 
		System.out.println(sub.findSubstring(s1, words1));

		String[] words2 = { "word", "good", "best", "good" }; 
		String s2 = "wordgoodgoodgoodbestword";

		System.out.println(sub.findSubstring(s2, words2));

	}

}
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
编辑 (opens new window)
#前缀树#滑动窗口
上次更新: 2024-05-21, 09:50:09
最近更新
01
LeetCode刷题工具之本地对拍
04-04
02
sublime对应语言模板使用技巧
02-28
03
经典字符串匹配算法
02-05
更多文章>
Theme by Vdoing | Copyright © 2020-2024 wuxin0011 | MIT License