java中如何找出01串中最长的子串?
时间: 2023-05-20 22:05:22 浏览: 82
可以使用动态规划来解决这个问题,具体步骤如下:
1. 定义状态:用 dp[i] 表示以第 i 个字符结尾的最长的 01 子串的长度。
2. 状态转移方程:如果第 i 个字符是 0,那么 dp[i] = dp[i-1] + 1;如果第 i 个字符是 1,那么 dp[i] = 0。
3. 初始状态:dp[0] = 0。
4. 最终结果:遍历 dp 数组,找到最大值即可。
以下是 Java 代码实现:
public int findMaxSubString(String s) {
int[] dp = new int[s.length()];
dp[0] = 0;
int max = 0;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == '0') {
dp[i] = dp[i-1] + 1;
} else {
dp[i] = 0;
}
max = Math.max(max, dp[i]);
}
return max;
}
相关问题
找出字符串中无重复最长子串-java实现
可以使用滑动窗口的思想来解决这个问题,具体实现如下:
```java
public static String longestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
String longest = "";
int left = 0, right = 0;
while (right < n) {
char c = s.charAt(right);
if (!set.contains(c)) {
set.add(c);
right++;
if (set.size() > longest.length()) {
longest = s.substring(left, right);
}
} else {
set.remove(s.charAt(left));
left++;
}
}
return longest;
}
```
该方法的时间复杂度为O(n),其中n为字符串s的长度。
Java找出两个字符串中所有共同的子串。
您好!关于您的问题,要找出两个字符串中所有共同的子串,可以采用暴力匹配法,对于其中一个字符串,逐个截取所有长度相同的子串,然后在另一个字符串中查找是否存在相同的子串,找到则记录下来即可。
代码示例:
```java
public static List<String> findCommonSubstrings(String s1, String s2) {
List<String> commonSubstrings = new ArrayList<>();
for (int i = 0; i < s1.length(); i++) {
for (int j = i + 1; j <= s1.length(); j++) {
String substring = s1.substring(i, j);
if (s2.indexOf(substring) != -1) {
commonSubstrings.add(substring);
}
}
}
return commonSubstrings;
}
```
注意,以上仅为一种常见的解法,实际上还存在更高效的算法,例如动态规划和后缀树等。