字符串经典题目

反转的几道经典题目

L344 字符串反转的相关题目

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间,你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。

示例 1:

输入:s = ["h","e","l","l","o"]
输出:["o","l","l","e","h"]

示例 2:

输入:s = ["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]

O(n)的时间复杂度解决,但是使用了位运算,这里的O(1)空间,指的是,不能使用额外的数组等来解决

class Solution {
    public void reverseString(char[] s) {

       for (int i = 0, j = s.length-1; i < j; i++, j--) {
            s[i] = (char)(s[i] ^ s[j]);
            s[j] = (char)(s[j] ^ s[i]);
            s[i] = (char)(s[i] ^ s[j]);
        }
    }
}

L541 反转字符串2

给定一个字符串 s 和一个整数 k,从字符串开头算起,每计数至 2k 个字符,就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个,则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样

示例 1:

输入:s = "abcdefg", k = 2
输出:"bacdfeg"

示例 2:

输入:s = "abcd", k = 2
输出:"bacd"

提示:

  • 1 <= s.length <= 104
  • s 仅由小写英文组成
  • 1 <= k <= 104

这道题注意一个条件: 如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样,也就是说我们计数反转的时候,还需要注意剩余字符串的数量

这里字符串的长度有两种情况:

  • 小于2K
  • 大于等于k

代码如下:

这里注意一点: 反转的方法是给定区间反转,因此需要index+k后再-1

class Solution {
    public String reverseStr(String s, int k) {
        int kk = k << 1;
        int sign = s.length() % kk;
        char[] ch = s.toCharArray();
        int index = 0;
        int len = s.length();
        while (len > sign) {
            reverse(ch, index, index + k-1);
            index += kk;
            len -= kk;
        }
        int revNum = sign < k ? s.length() - 1 : index + k-1;
        reverse(ch, index, revNum);
        return new String(ch);
    }
    private static void reverse(char[] s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            s[i] = (char) (s[i] ^ s[j]);
            s[j] = (char) (s[j] ^ s[i]);
            s[i] = (char) (s[i] ^ s[j]);
        }
    }

}

优化:

简单优化是while条件少几次计算:

   int w = len-sign;
while (index<w) {
            reverse(ch, index, index + k-1);
            index += kk;
        
        }

但是变量定义也可以优化,最终:

class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        int index = 0;
        int len = s.length();
        while (index < len) {
            reverse(ch, index, Math.min(index + k - 1, s.length() - 1));
            index += k << 1;
        }
        return new String(ch);
    }

    private static void reverse(char[] s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            s[i] = (char) (s[i] ^ s[j]);
            s[j] = (char) (s[j] ^ s[i]);
            s[i] = (char) (s[i] ^ s[j]);
        }
    }

}

L917 仅仅反转字母

给你一个字符串 s ,根据下述规则反转字符串:

  • 所有非英文字母保留在原有位置。
  • 所有英文字母(小写或大写)位置反转。

示例 1:

输入:s = "ab-cd"
输出:"dc-ba"

示例 2:

输入:s = "a-bC-dEf-ghIj"
输出:"j-Ih-gfE-dCba"

示例 3:

输入:s = "Test1ng-Leet=code-Q!"
输出:"Qedo1ct-eeLg=ntse-T!"

这里可以参考快速排序中的哨兵机制(也不知道怎么说),代码实现如下,但是这里注意,最外层的循环不需要对i``j进行操作,并且最后需要对交换位置进行判断是否i<j

class Solution {
    public String reverseOnlyLetters(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        char[] ch = s.toCharArray();
        int i = 0, j = ch.length - 1;
        while (i < j) {
            // 跳过非字母字符
            while (i < j && !Character.isLetter(ch[i])) {
                i++;
            }
            while (i < j && !Character.isLetter(ch[j])) {
                j--;
            }
            // 交换字符
            if (i < j) {
                char temp = ch[i];
                ch[i] = ch[j];
                ch[j] = temp;
                i++;
                j--;
            }
        }
        return new String(ch);
    }
}

这里的isLetter方法源码非常优雅,可以去看看

另一种方法: 栈

将 s 中的所有字母单独存入栈中,所以出栈等价于对字母反序操作。(或者,可以用数组存储字母并反序数组。)
然后,遍历 s 的所有字符,如果是字母我们就选择栈顶元素输出

class Solution {
    public String reverseOnlyLetters(String S) {
    
        Stack<Character> letters = new Stack();
        for (char c: S.toCharArray())
            if (Character.isLetter(c))
                letters.push(c);

        StringBuilder ans = new StringBuilder();
        for (char c: S.toCharArray()) {
            if (Character.isLetter(c))
                ans.append(letters.pop());
            else
                ans.append(c);
        }

        return ans.toString();
    }
}

这里的代码也很好实现,唯一可能会想错的一点是,加入到栈内的时候,只需要加入字母,因此,在生成ans结果的时候,也就不需要考虑是否为字母了。(只需要迭代原来的字符串,遇见字母从栈取即可

L151 反转字符串中的单词

给你一个字符串 s ,请你反转字符串中 单词 的顺序。

  • 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
  • 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

**注意:**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。

提示:

  • 1 <= s.length <= 104
  • s 包含英文大小写字母、数字和空格 ' '
  • s至少存在一个 单词

方法一:API方法

这里需要注意的只有API的熟悉程度

  • split: \\s+匹配多个空白字符串换行符等,第一个\是转义
  • join: 给集合或者字符串拼接,这里使用集合List

官方贴图:

image-20240322124038446

class Solution {
    public String reverseWords(String s) {
        if (s == null || s.isEmpty()) {
            return s;
        }
        List<String> list = Arrays.asList(s.trim().split("\\s+"));
        Collections.reverse(list);
        return String.join(" ", list);
    }
}

方法二: 不借助API使用双指针

这里写出一个效率很高的思路:

j和i最初位置都放在s.length()-1

image-20240322124635782

这里注意:

  1. 构造res直接构造最终结果就行,可以直接添加好“ ”
  2. 最终多余的一个末尾“ ”,可以直接使用trim(),无需多余操作
class Solution {
    public String reverseWords(String s) {
        if (s == null || s.isEmpty()) {
            return s;
        }
        s = s.trim();
        int i = s.length() - 1, j = i;
        StringBuilder res = new StringBuilder();
        while (i >= 0) {
            while (i >= 0 && s.charAt(i) != ' ') {
                i--;
            }
            res.append(s.substring(i + 1, j + 1) + " ");
            while (i >= 0 && s.charAt(i) == ' ') {
                i--;
                j = i;
            }
        }
        return res.toString().trim();

    }
}

这里的trim()JDK方法的实现值得参考:

public static String trim(byte[] value) {
        int length = value.length >> 1;
        int len = length;
        int st = 0;
        while (st < len && getChar(value, st) <= ' ') {
            st++;
        }
        while (st < len && getChar(value, len - 1) <= ' ') {
            len--;
        }
        return ((st > 0) || (len < length )) ?
            new String(Arrays.copyOfRange(value, st << 1, len << 1), UTF16) :
            null;
    }

L125 验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个 回文串

字母和数字都属于字母数字字符。

给你一个字符串 s,如果它是 回文串 ,返回 true ;否则,返回 false

示例 1:

输入: s = "A man, a plan, a canal: Panama"
输出:true
解释:"amanaplanacanalpanama" 是回文串。

示例 2:

输入:s = "race a car"
输出:false
解释:"raceacar" 不是回文串。

示例 3:

输入:s = " "
输出:true
解释:在移除非字母数字字符之后,s 是一个空字符串 "" 。
由于空字符串正着反着读都一样,所以是回文串。

提示:

  • 1 <= s.length <= 2 * 105
  • s 仅由可打印的 ASCII 字符组成

双指针

这道题两种思路:直接进行判断,或者转换为统一不含字符进行判断,这里双指针直接判断:

  • isLetterOrDigit()是判断是字母或者数字直接返回
  • if (i < j)这需要在此判断,因为如果不含字母数字,也是true,这里再次判断也是为了防止此时两个指针还未遇到,进行比较
class Solution {
    public boolean isPalindrome(String s) {

        int len = s.length();
        for (int i = 0, j = len - 1; i < j; i++, j--) {
            while (i < j && !Character.isLetterOrDigit(s.charAt(i))) {
                i++;
            }
            while (i < j && !Character.isLetterOrDigit(s.charAt(j))) {
                j--;
            }
            if (i < j) {
                if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
                    return false;
                }
            }
        }
        return true;

    }
}

先转换

这里是先将字母或者数字直接加入stringBuilder中,然后反转与原字符串进行比较,是最容易想到的方法之一

class Solution {
    public boolean isPalindrome(String s) {
        StringBuffer sgood = new StringBuffer();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (Character.isLetterOrDigit(ch)) {
                sgood.append(Character.toLowerCase(ch));
            }
        }
        StringBuffer sgood_rev = new StringBuffer(sgood).reverse();
        return sgood.toString().equals(sgood_rev.toString());
    }
}

L387 字符串中的第一个唯一字符

给定一个字符串 s ,找到 它的第一个不重复的字符,并返回它的索引 。如果不存在,则返回 -1

示例 1:

输入: s = "leetcode"
输出: 0

示例 2:

输入: s = "loveleetcode"
输出: 2

示例 3:

输入: s = "aabb"
输出: -1

提示:

  • 1 <= s.length <= 105
  • s 只包含小写字母

使用hashmap的API:

class Solution {
    public int firstUniqChar(String s) {
        HashMap<Character,Integer> hashMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            hashMap.put(s.charAt(i),hashMap.getOrDefault(s.charAt(i),0)+1);
        }
        for (int i = 0; i < s.length(); i++) {
            if (hashMap.get(s.charAt(i))==1){
                return i;
            }
        }
        return -1;
    }
}

推荐:一般情况,尽量不要使用API库,因为那样会降低很多的效率

class Solution {
    public int firstUniqChar(String s) {
        HashMap<Character,Integer> hashMap = new HashMap<>();
        int[] arr = new int[26];
        int n = s.length();
        for (int i = 0; i < n; i++) {
            arr[s.charAt(i)-'a']++ ;
        }
        for (int i = 0; i < n; i++) {
            if (arr[s.charAt(i)-'a']==1){
                return i;
            }
        }
        return -1;
    }
}

另一中IndexOf解法:

这里的解法最核心的是if中的三个条件:

  • n!=1: 这里好理解,意思就是首先字母要在字符串中存在
  • n == s.lastIndexOf(c): 这里是在字符串中不能存在
  • n < min: 这里很重要,意思是只能在当前字符串中找到到索引前寻找,比如:tbtdahj,找到a的索引后,将min的值换为a的索引,接下来寻找不重复的字符串,只能在a索引左边寻找,也就是可以找到第一个出现的字符b
class Solution {
    public int firstUniqChar(String s) {
        int min = Integer.MAX_VALUE;
        for(char c = 'a'; c <= 'z'; c++) {
            int n = s.indexOf(c);
            if(n != -1 && n == s.lastIndexOf(c) && n < min) {
                min = n;
            }
        }
        return min < s.length() ? min : -1;
    }
}

L242 判定是否互为字符重排

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

**注意:**若 st 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

提示:

  • 1 <= s.length, t.length <= 5 * 104
  • st 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?

记录一个异或解法: 但是这个方法基于两个字符串字符出现次数一样,因此这里并不适用

  public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()){
            return false;
        }
        int flag =0;
        for (int i = 0; i < s.length(); i++) {
            flag ^= s.charAt(i)^t.charAt(i);
        }
        return 0==flag;
    }

因此这里有两种解法:

排序后重组

这个方法效率相对较快,实现也简单

class Solution {
     public boolean isAnagram(String s1, String s2) {
       // 将字符串转换成字符数组
        char[] s1Chars = s1.toCharArray();
        char[] s2Chars = s2.toCharArray();
        // 对字符数组进行排序
        Arrays.sort(s1Chars);
        Arrays.sort(s2Chars);
        // 再将字符数组转换成字符串,比较是否相等
        return new String(s1Chars).equals(new String(s2Chars));
    }
}

HashMap计算次数

这种方法并不推荐,效率比较慢

public boolean checkPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        char[] s1Chars = s1.toCharArray();
        Map<Character, Integer> s1Map = getMap(s1);
        Map<Character, Integer> s2Map = getMap(s2);
        for (char s1Char : s1Chars) {
            if (!s2Map.containsKey(s1Char) || (int)s2Map.get(s1Char) != (int)s1Map.get(s1Char)) {
                return false;
            }
        }
        return true;
    }

    // 统计指定字符串str中各字符的出现次数,并以Map的形式返回
    private Map<Character, Integer> getMap(String str) {
        Map<Character, Integer> map = new HashMap<>();
        char[] chars = str.toCharArray();
        for (char aChar : chars) {
            map.put(aChar, map.getOrDefault(aChar, 0) + 1);
        }
        return map;
    }

这里也可以使用数组实现:

class Solution {
    boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        int[] hash = new int[26];
        for (int i = 0; i < s.length(); i++) {
            hash[s.charAt(i) - 'a']++;
            hash[t.charAt(i) - 'a']--;
        }

        for (int i : hash) {
            if (i != 0) {
                return false;
            }
        }

        return true;
    }
}