leetcode刷题（字符串）

本文主要是介绍leetcode刷题（字符串），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 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”]

# python
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left, right = 0, len(s) - 1
        while(left < right):
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

// Java
class Solution {
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while (left < right) {
            s[left] ^= s[right];
            s[right] ^= s[left];
            s[left] ^= s[right];
            left++;
            right--;
        }
    }
}

反转字符串II

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

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

示例 1：
输入：s = “abcdefg”, k = 2
输出：“bacdfeg”

示例 2：
输入：s = “abcd”, k = 2
输出：“bacd”

# python
class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        def reverse_substring(text):
            left, right = 0, len(text) - 1
            while left < right:
                text[left], text[right] = text[right], text[left]
                left += 1
                right -= 1
            return text
        res = list(s)
        for i in range(0, len(s), 2 * k):
            res[i:i+k] = reverse_substring(res[i:i+k])	# python切片取出剩余的部分，不会报超出索引
        return ''.join(res)

# Java
class Solution {
    public String reverseStr(String s, int k) {
        char[] res = s.toCharArray();
        for (int i = 0; i < res.length; i += 2 * k) {
            if (i + k <= res.length) {
                reverse_substring(res, i, i + k - 1);
            } else {
                reverse_substring(res, i, res.length - 1);
            }
        }
        return new String(res);
    }
    public void reverse_substring(char[] text, int i, int j) {
        for (; i < j; i++, j--) {
            text[i] ^= text[j];
            text[j] ^= text[i];
            text[i] ^= text[j];
        }
    }
}

替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1：
输入：s = “We are happy.”
输出：“We%20are%20happy.”

# python
class Solution:
    def replaceSpace(self, s: str) -> str:
        counter = s.count(' ')
        res = list(s)
        res.extend([' '] * 2 * counter)
        left, right = len(s) - 1, len(res) - 1
        while left >= 0:
            if res[left] != ' ':
                res[right] = res[left]
                right -= 1
            else:
                res[right - 2 : right + 1] = '%20'
                right -= 3
            left -= 1
        return ''.join(res)

// Java
class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            // str.charAt(i) 为 char 类型
            if (s.charAt(i) != ' ') {
                sb.append(s.charAt(i));
            } else {
                sb.append("%20");
            }
        }
        return sb.toString();
    }
}

翻转字符串里的单词

给你一个字符串 s ，逐个翻转字符串中的所有单词。

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

说明：
输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
翻转后单词间应当仅用一个空格分隔。
翻转后的字符串中不应包含额外的空格。

示例 1：
输入：s = “the sky is blue”
输出：“blue is sky the”

示例 2：
输入：s = " hello world "
输出：“world hello”
解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。

# pyhton
class Solution:
    def reverseWords(self, s: str) -> str:
        res = self.trim_space(s)
        self.reverse_string(res, 0, len(res) - 1)
        self.reverse_each_word(res)
        return ''.join(res)

    def trim_space(self, s): 
        res = []
        left, right = 0, len(s) - 1
        while s[left] == ' ':  left += 1
        while s[right] == ' ':  right -= 1
        while left <= right:
            if s[left] != ' ':
                res.append(s[left])
            elif res[-1] != ' ':
                res.append(s[left])
            left += 1
        return res

    def reverse_string(self, s, left, right):   # 使用是s[left:right+1]切片的方式无法对原数组进行翻转.
        while(left < right):
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1
        return None 

    def reverse_each_word(self, s):
        left, right = 0, 0
        while left < len(s):
            while right<len(s) and s[right] != ' ':
                right += 1
            self.reverse_string(s, left, right - 1)
            right += 1
            left = right

// Java
// 在Java中用StringBuilder来实现，如果按照python的思路，将字符串转成数组实现会提示内存超出限制。
class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = removeSpace(s);
        reverseString(sb, 0, sb.length() - 1);
        reverseEachWord(sb);
        return sb.toString();

    }
    private StringBuilder removeSpace(String s) {
        int left = 0, right = s.length() - 1;
        while (s.charAt(left) == ' ') left++;
        while (s.charAt(right) == ' ') right--;
        StringBuilder sb = new StringBuilder();
        while (left <= right) {
            char c = s.charAt(left);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            left++;
        }
        return sb;
    }
    private void reverseString(StringBuilder sb, int left, int right) {
        while (left < right) {
            char tmp = sb.charAt(left);
            sb.setCharAt(left, sb.charAt(right));
            sb.setCharAt(right, tmp);
            left++;
            right--;
        }
    }
    private void reverseEachWord(StringBuilder sb) {
        int left = 0, right = 0;
        while (left < sb.length()) {
            while (right < sb.length() && sb.charAt(right) != ' ') {
                right++;
            }
            reverseString(sb, left, right - 1);
            right++;
            left = right;
        }
    }
}

左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1：
输入: s = “abcdefg”, k = 2
输出: “cdefgab”

示例 2：
输入: s = “lrloseumgh”, k = 6
输出: “umghlrlose”

# python
class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        def reverse_sub (s, left, right):
            while left < right:
                s[left], s[right] = s[right], s[left]
                left += 1
                right -= 1
        res = list(s)
        reverse_sub(res, 0, n - 1)
        reverse_sub(res, n, len(res) - 1)
        reverse_sub(res, 0, len(res) - 1)
        return ''.join(res)

// Java
class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder sb = new StringBuilder(s);
        reverseString(sb, 0, n - 1);
        reverseString(sb, n, s.length() - 1);
        return sb.reverse().toString();

    }
    public void reverseString(StringBuilder sb, int left, int right) {
        while (left < right) {
            char tmp = sb.charAt(left);
            sb.setCharAt(left, sb.charAt(right));
            sb.setCharAt(right, tmp);
            left++;
            right--;
        }
    }
}

实现strStr()

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1：
输入：haystack = “hello”, needle = “ll”
输出：2

示例 2：
输入：haystack = “aaaaa”, needle = “bba”
输出：-1

示例 3：
输入：haystack = “”, needle = “”
输出：0

KMP算法：在一个串中查找是否出现过另一个串，可以使用KMP来降低复杂度。当出现不匹配的情况事，KMP不是从头开始匹配，而是利用前面已经匹配过的字符串来接着判断是否匹配。KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。B站视频讲解

# python
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if len(needle) == 0:
            return 0
        next = self.getNext(needle)
        j = 0
        for i in range(len(haystack)):
            while(j > 0 and needle[j] != haystack[i]):
                j = next[j - 1]
            if(needle[j] == haystack[i]):
                j += 1
            if(j == len(needle)):
                return i - j + 1
        return -1

    def getNext(self, s):
        # 1. 初始化 i为后缀末尾，j为前缀末尾
        j = 0
        next = ['' for i in range(len(s))]
        next[0] = 0
        for i in range(1, len(s)):	# i为后缀末尾，后缀不包括第一个字符，故i要从1开始
            # 2. s[i] != s[j]   回退
            while(j > 0 and s[i] != s[j]):
                j = next[j - 1]
            # 3. s[i] == s[j]   j++
            if(s[i] == s[j]):
                j += 1
            # 4. 更新next[]数组
            next[i] = j
        return next

// Java
class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) {
            return 0;
        }
        int j = 0;
        int[] next = getNext(needle);
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == needle.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }
    public int[] getNext(String s) {
        int[] next = new int[s.length()];
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}

重复的子字符串

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:
输入: “abab”
输出: True
解释: 可由子字符串 “ab” 重复两次构成。

示例 2:
输入: “aba”
输出: False

示例 3:
输入: “abcabcabcabc”
输出: True
解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)

如果数组长度len % (len - (next[len - 1] + 1)) == 0 ，则说明 (数组长度-最长相等前后缀的长度) 正好可以被数组的长度整除，说明有该字符串有重复的子字符串。
数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。
把next数组打印出来，看看next数组里的规律，有助于理解KMP算法。
在这里插入图片描述

# python
class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        next = self.getNext(s)
        if next[-1] != 0 and len(s) % (len(s) - next[-1]) == 0:
            return True
        else:
            return False

    def getNext(self, s):
        next = [0] * len(s)
        j = 0
        for i in range(1, len(s)):
            while j > 0 and s[i] != s[j]:
                j = next[j - 1]
            if s[i] == s[j]:
                j += 1
            next[i] = j
        return next

// Java
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int[] next = getNext(s);
        int len = s.length();
        if (next[len - 1] != 0 && len % (len - next[len - 1]) == 0) {
            return true;
        } else {
            return false;
        }

    }
    public int[] getNext(String s) {
        int[] next = new int[s.length()];
        int j = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}

这篇关于leetcode刷题（字符串）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

C/C++教程

leetcode刷题（字符串）

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯