用Jdk1.8编写在一个由小写英文字母(a-z)组成的字符串中,查找最短子串 其头尾字母相同。输出最左边的该类子串 输入说明:待处理字串(长度≤200) 输出说明:子串 输入样例:dfasjdoiasldhlfa 输出样例:ldhl
时间: 2024-12-14 13:16:08 浏览: 9
推荐一款JDK1.8版本非常好用-jdk-8u361-windows-x64
3星 · 编辑精心推荐
在 Java 8 中,你可以使用滑动窗口(Sliding Window)的概念来解决这个问题。这个算法的主要思想是从左到右遍历字符串,每次移动一个字符,检查当前窗口两端的字母是否相等,如果相等则更新结果。以下是实现的一个示例:
```java
public class ShortestSubstringWithSameStartAndEnd {
public String shortestSubstr(String s) {
if (s == null || s.length() <= 1) return s;
int start = 0, len = 0; // 子串起始位置和长度
char leftChar = s.charAt(0); // 窗口左侧的字符
for (int i = 1; i < s.length(); i++) {
if (leftChar == s.charAt(i)) { // 如果新字符与左端字符相同
len++;
if (i - start > len) { // 更新最长子串
start = i - len;
}
} else { // 否则,开始新的窗口
start = i;
leftChar = s.charAt(i);
len = 1;
}
}
return s.substring(start, start + len);
}
public static void main(String[] args) {
String input = "dfasjdoiasldhlfa";
ShortestSubstringWithSameStartAndEnd ssse = new ShortestSubstringWithSameStartAndEnd();
System.out.println(ssse.shortestSubstr(input)); // 输出: ldhl
}
}
```
在这个例子中,我们遍历输入字符串,如果找到一个子串的首尾字符相同,并且这个子串比之前发现的所有相等子串更长,我们就更新最短子串的起点。当遇到不匹配的字符时,我们将窗口重置到当前位置。
阅读全文