字节跳动字符串挑战题集，从基础概念到实际问题。
无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例1：
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例2：
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例3：
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
思路
使用HashSet作为滑动窗口，我们可以用O(1)的时间来完成对字符是否在当前的子字符串中的检查。
我们使用 HashSet 将字符存储在当前窗口 [i, j)[i,j)（最初 j = ij=i）中。 然后我们向右侧滑动索引 jj，如果它不在 HashSet 中，我们会继续滑动 jj。直到 s[j] 已经存在于 HashSet 中。此时，我们找到的没有重复字符的最长子字符串将会以索引 ii 开头。如果我们对所有的 ii 这样做，就可以得到答案。
代码
方法 滑动窗口法
class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
Set<Character> set = new HashSet<>();
int ans=0, i=0, j=0;
while(i < len && j < len){
if(!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
ans = Math.max(ans,j-i);
}else{
set.remove(s.charAt(i++));
}
}
return ans;
}
}
最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ““。
示例1：
输入: ["flower","flow","flight"]
输出: "fl"
示例2： 输入: [“dog”,”racecar”,”car”] 输出: “” 解释: 输入不存在公共前缀。
思路
令最长公共前缀ans的值为第一个字符串，进行初始化，而后遍历后面的字符串，依次将其与ans进行比较，两两找出公共前缀，最终结果即为最长公共前缀。
代码
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length == 0)
return "";
String ans = strs[0];
for(int i =1;i<strs.length;i++) {
int j=0;
for(;j<ans.length() && j < strs[i].length();j++) {
if(ans.charAt(j) != strs[i].charAt(j))
break;
}
ans = ans.substring(0, j);
if(ans.equals(""))
return ans;
}
return ans;
}
}
字符串排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。 换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1：
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例2：
输入: s1= "ab" s2 = "eidboaoo"
输出: False
注意
- 输入的字符串只包含小写字母
- 两个字符串的长度都在 [1, 10,000] 之间
思路
滑动窗口
代码
package com.moxuanran.algorithm.string;
/**
* 字符串排列
* <p>
* 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
* 换句话说，第一个字符串的排列之一是第二个字符串的子串。
* <p>
* <p>
* 注意：
* 输入的字符串只包含小写字母
* 两个字符串的长度都在 [1, 10,000] 之间
*
* @author 莫轩然
* @date 2020-03-07
*/
public class Arrangement {
private boolean checkInclusion(String s1, String s2) {
//合法性校验
if (s1.length() > s2.length()) {
return false;
}
//初始化两个数组,分别统计
int[] s1map = new int[26];
int[] s2map = new int[26];
//首先明确，如果是排列，那么长度必然相等，按照s1长度初始化数组
for (int i = 0; i < s1.length(); i++) {
s1map[s1.charAt(i) - 'a']++;
s2map[s2.charAt(i) - 'a']++;
}
//滑动窗口，依次匹配
for (int i = 0; i < s2.length() - s1.length(); i++) {
if (matches(s1map, s2map)) {
return true;
}
s2map[s2.charAt(i + s1.length()) - 'a']++;
s2map[s2.charAt(i) - 'a']--;
}
return false;
}
/**
* 匹配两字符串是否为排列，核心思想：排列必然所有字符出现的次数一致
* @param s1map 短串
* @param s2map 长串
* @return boolean
*/
private boolean matches(int[] s1map, int[] s2map) {
for (int i = 0; i < 26; i++) {
if (s1map[i] != s2map[i]) {
return false;
}
}
return true;
}
public static void main(String[] args){
//测试用例
String s1 = "ab";
String s2 = "eidbaooo";
Arrangement arrangement = new Arrangement();
boolean result = arrangement.checkInclusion(s1,s2);
System.out.println("s1是否为s2的排列:" + result);
}
}
翻转字符串里的单词
给定一个字符串，逐个翻转字符串中的每个单词。
示例1：
输入: "the sky is blue"
输出: "blue is sky the"
示例2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
说明：
- 无空格字符构成一个单词。
- 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
- 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个
代码
方法1：采用Java语言特性
class Solution {
public String reverseWords(String s) {
// 除去开头和末尾的空白字符
s = s.trim();
// 正则匹配连续的空白字符作为分隔符分割
List<String> wordList = Arrays.asList(s.split("\\s+"));
Collections.reverse(wordList);
return String.join(" ", wordList);
}
}
方法2：双指针+栈
class Solution {
public String reverseWords(String s) {
int startIndex = 0, endIndex = 0;//左闭右开
String newS = s.trim();
Stack<String> wordStack = new Stack<>();
//将单词放入栈中
while (!newS.isEmpty()) {
startIndex = 0;
endIndex = 0;
while (endIndex < newS.length() && ' ' != newS.charAt(endIndex)) {
endIndex++;
}
wordStack.add(newS.substring(startIndex, endIndex));
newS = newS.substring(endIndex).trim();
}
//从栈中取出，拼凑输出
StringBuilder result = new StringBuilder();
while (!wordStack.isEmpty()) {
result.append(wordStack.pop()).append(" ");
}
return result.toString().trim();
}
}