题目描述

C 语言有一个库函数： char *strstr(const char *haystack, const char *needle) ，实现在字符串 haystack 中查找第一次出现字符串 needle 的位置，如果未找到则返回 null。

现要求实现一个 strstr 的增强函数，可以使用带可选段的字符串来模糊查询，与strstr 一样返回首次查找到的字符串位置。

可选段使用 [] 标识，表示该位置是可选段中任意一个字符即可满足匹配条件。比如“a[bc]” 表示可以匹配 “ab” 或 “ac”。

注意目标字符串中可选段可能出现多次。

输入描述 与 strstr 函数一样，输入参数是两个字符串指针，分别是源字符串和目标字符串。

输出描述 与 strstr 函数不同，返回的是源字符串中，匹配子字符串相对于源字符串地址的偏移（从 0 开始算），如果没有匹配返回 -1。

补充说明：源字符串中必定不包含 []；目标字符串中 [] 必定成对出现，且不会出现嵌套。

输入的字符串长度在 [1,100] 之间。

示例1

输入

abcd
b[cd]

输出

1

解题思路

1. 遍历源字符串： 从源字符串的每个位置开始，尝试匹配目标字符串。
2. 匹配逻辑：

• 普通字符匹配：目标字符串中的普通字符需要和源字符串的对应字符完全匹配。
• 可选段匹配：
  • 当目标字符串中出现方括号[时，识别为可选段的开始。
  • 读取可选段中的字符，检查源字符串的当前字符是否在可选字符列表中。
  • 如果源字符串的字符匹配可选段中存在，则继续匹配下一个字符；否则，匹配失败。
  • 继续匹配目标字符串中方括号[]后的字符。

3. 返回匹配结果：

• 如果从某个位置开始的匹配成功，返回该位置的索引。
• 如果遍历了源字符串的所有位置都没有找到匹配，返回 -1

源码 Java

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

public class EnhanceStrStr {

	public Input input = new Input("abcd\nb[cd]");
	@BeforeEach
	public void init() {
		input = new Input("abcd\ndb[cd]");
	}
	@Test
	public void test() {
		String source = input.nextLine();
		String needle = input.nextLine();
		int i = indexOf(source, needle);
		System.out.println(i);
	}

	public static int indexOf(String source, String needle) {
		int sourceLength = source.length();
		int needleLength = needle.length();

		for (int i = 0;i < sourceLength;i++) {
			int matchFrom = i;
			boolean found = true;
			for (int j = 0;j < needleLength;) {
				// source String 已经遍历完成 needle 没有遍历完成，表示没有匹配的字符串
				if (matchFrom >= sourceLength) {
					found = false;
					break;
				}
				boolean regmatch = false ;
				// 通配开始标志 默认没有匹配，如果发现则修改为 true
				if ('[' == needle.charAt(j)) {
					// 找到 ] 表示通配符匹配结束
					while (needle.charAt(j++) != ']') {
						if (source.charAt(matchFrom) == needle.charAt(j)) {
							regmatch  = true;
						}
					}
					// 结束后没有匹配字符，跳出匹配 从 source 字符串的下一个字符重新开始查找 i++
					if (!regmatch) {
						break;
					}
				} else {
					// 如果字符相等两个指针都向后移动
					if (source.charAt(matchFrom) == needle.charAt(j)) {
						matchFrom++;
						j++;
					} else {
						// 字符不匹配 从 source 字符串的下一个字符重新开始查找 i++
						found = false;
						break;
					}
				}
			}
			// 对比完成后没有被设置为 false 则说明有对应的字符串
			if (found) {
				return i;
			}
		}
		return -1;
	}
}

class Input {
	public String[] lines;
	public int index = 0;
	public Input(String lines) {
		this.lines = lines.split("\n");
	}
	public String nextLine() {
		return lines[index++];
	}
}