字符串题解方法

作者: ML李嘉图

反转字符串

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

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

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1:

输入:[“h”,“e”,“l”,“l”,“o”]

输出:[“o”,“l”,“l”,“e”,“h”]

class Solution {
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length - 1;
        while (l < r) {
            s[l] ^= s[r];  //构造 a ^ b 的结果,并放在 a 中
            s[r] ^= s[l];  //将 a ^ b 这一结果再 ^ b ,存入b中,此时 b = a, a = a ^ b
            s[l] ^= s[r];  //a ^ b 的结果再 ^ a ,存入 a 中,此时 b = a, a = b 完成交换
            l++;
            r--;
        }
    }
}

反转字符串II

给定一个字符串 s 和一个整数 k,你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。

如果剩余字符少于 k 个,则将剩余字符全部反转。

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

示例:

输入: s = “abcdefg”, k = 2

输出: “bacdfeg”

//解法一
class Solution {
    public String reverseStr(String s, int k) {
        StringBuffer res = new StringBuffer();
        int length = s.length();
        int start = 0;
        while (start < length) {
            // 找到k处和2k处
            StringBuffer temp = new StringBuffer();
            // 与length进行判断,如果大于length了,那就将其置为length
            int firstK = (start + k > length) ? length : start + k;
            int secondK = (start + (2 * k) > length) ? length : start + (2 * k);
            //无论start所处位置,至少会反转一次
            temp.append(s.substring(start, firstK));
            res.append(temp.reverse());
            // 如果firstK到secondK之间有元素,这些元素直接放入res里即可。
            if (firstK < secondK) { //此时剩余长度一定大于k。
                res.append(s.substring(firstK, secondK));
            }
            start += (2 * k);
        }
        return res.toString();
    }
}
//解法二(似乎更容易理解点)
//题目的意思其实概括为 每隔2k个反转前k个,尾数不够k个时候全部反转
class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        for(int i = 0; i < ch.length; i += 2 * k){
            int start = i;
            //这里是判断尾数够不够k个来取决end指针的位置
            int end = Math.min(ch.length - 1, start + k - 1);
            //用异或运算反转 
            while(start < end){
                ch[start] ^= ch[end];
                ch[end] ^= ch[start];
                ch[start] ^= ch[end];
                start++;
                end--;
            }
        }
        return new String(ch);
    }
}
// 解法3
class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        // 1. 每隔 2k 个字符的前 k 个字符进行反转
        for (int i = 0; i< ch.length; i += 2 * k) {
            // 2. 剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符
            if (i + k <= ch.length) {
                reverse(ch, i, i + k -1);
                continue;
            }
            // 3. 剩余字符少于 k 个,则将剩余字符全部反转
            reverse(ch, i, ch.length - 1);
        }
        return  new String(ch);
    }
    // 定义翻转函数
    public void reverse(char[] ch, int i, int j) {
    for (; i < j; i++, j--) {
        char temp  = ch[i];
        ch[i] = ch[j];
        ch[j] = temp;
    }
    }
}

替换空格

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

示例 1: 输入:s = “We are happy.”

输出:“We%20are%20happy.”

这么做有两个好处:

  1. 不用申请新数组。
  2. 从后向前填充元素,避免了从前先后填充元素要来的 每次添加元素都要将添加元素之后的所有元素向后移动。
    //使用一个新的对象,复制 str,复制的过程对其判断,是空格则替换,否则直接复制,类似于数组复制
    public static String replaceSpace(StringBuffer str) {
        if (str == null) {
            return null;
        }
        //选用 StringBuilder 单线程使用,比较快,选不选都行
        StringBuilder sb = new StringBuilder();
        //使用 sb 逐个复制 str ,碰到空格则替换,否则直接复制
        for (int i = 0; i < str.length(); i++) {
        //str.charAt(i) 为 char 类型,为了比较需要将其转为和 " " 相同的字符串类型
            if (" ".equals(String.valueOf(str.charAt(i)))){
                sb.append("%20");
                sb.append(str.charAt(i));
            }
        }
        return sb.toString();
    }
    

翻转字符串

翻转字符串里的单词给定一个字符串,逐个翻转字符串中的每个单词。

示例 1:

输入: “the sky is blue”

输出: “blue is sky the” 不要使用辅助空间,空间复杂度要求为O(1)。

所以解题思路如下:

  • 移除多余空格
  • 将整个字符串反转
  • 将每个单词反转

举个例子,源字符串为:“the sky is blue "

  • 移除多余空格 : “the sky is blue”
  • 字符串反转:“eulb si yks eht”
  • 单词反转:“blue is sky the”

这样们就完成了翻转字符串里的单词。

class Solution {
   /**
     * 不使用Java内置方法实现
     * <p>
     * 1.去除首尾以及中间多余空格
     * 2.反转整个字符串
     * 3.反转各个单词
     */
    public String reverseWords(String s) {
        // System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
        // 1.去除首尾以及中间多余空格
        StringBuilder sb = removeSpace(s);
        // 2.反转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        // 3.反转各个单词
        reverseEachWord(sb);
        return sb.toString();
    }
    private StringBuilder removeSpace(String s) {
        // System.out.println("ReverseWords.removeSpace() called with: s = [" + s + "]");
        int start = 0;
        int end = s.length() - 1;
        while (s.charAt(start) == ' ') start++;
        while (s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        while (start <= end) {
            char c = s.charAt(start);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start++;
        }
        // System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]");
        return sb;
    }
    /**
     * 反转字符串指定区间[start, end]的字符
     */
    public void reverseString(StringBuilder sb, int start, int end) {
        // System.out.println("ReverseWords.reverseString() called with: sb = [" + sb + "], start = [" + start + "], end = [" + end + "]");
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
        // System.out.println("ReverseWords.reverseString returned: sb = [" + sb + "]");
    }
    private void reverseEachWord(StringBuilder sb) {
        int start = 0;
        int end = 1;
        int n = sb.length();
        while (start < n) {
            while (end < n && sb.charAt(end) != ' ') {
                end++;
            }
            reverseString(sb, start, end - 1);
            start = end + 1;
            end = start + 1;
        }
    }
}

左旋转字符串

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

示例 1:

输入: s = “ab cdefg”, k = 2

输出: “cdefg ab” 不能申请额外空间,只能在本串上操作

可以通过局部反转+整体反转 达到左旋转的目的。

具体步骤为:

  1. 反转区间为前n的子串
  2. 反转区间为n到末尾的子串
  3. 反转整个字符串

最后就可以得到左旋n的目的,而不用定义新的字符串,完全在本串上操作。

class Solution {
    public String reverseLeftWords(String s, int n) {
        int len=s.length();
        StringBuilder sb=new StringBuilder(s);
        reverseString(sb,0,n-1);
        reverseString(sb,n,len-1);
        return sb.reverse().toString();
    }
     public void reverseString(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
            }
        }
}

实现 strStr()

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。

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

KMP算法

K nuth-M orris-P ratt 字符串查找算法,简称为 KMP算法,常用于在一个文本串 S 内查找一个模式串 P 的出现位置。

KMP有什么用

KMP主要应用在字符串匹配上。 KMP的主要思想是当出现字符串不匹配时,可以知道一部分之前已经匹配的文本内容,可以利用这些信息避免从头再去做匹配了。

什么是前缀表

next数组就是一个前缀表(prefix table)。 前缀表有什么作用呢? 前缀表是用来回退的,它记录了模式串与主串(文本串)不匹配的时候,模式串应该从哪里开始重新匹配。

很多KMP算法的时间都是使用next数组来做回退操作, next数组就可以是前缀表,很多实现都是把前缀表统一减一(右移一位,初始位置为-1)之后作为next数组。

时间复杂度分析

其中n为文本串长度,m为模式串长度,因为在匹配的过程中,根据前缀表不断调整匹配的位置,可以看出匹配的过程是O(n),之前还要单独生成next数组,时间复杂度是O(m)。

所以整个KMP算法的时间复杂度是O(n+m)的。

暴力的解法显而易见是O(n * m),所以KMP在字符串匹配中极大的提高的搜索的效率。

代码

class Solution {
    /**
     * 基于窗口滑动的算法
     * <p>
     * 时间复杂度:O(m*n)
     * 空间复杂度:O(1)
     * 注:n为haystack的长度,m为needle的长度
     */
    public int strStr(String haystack, String needle) {
        int m = needle.length();
        // 当 needle 是空字符串时们应当返回 0
        if (m == 0) {
            return 0;
        }
        int n = haystack.length();
        if (n < m) {
            return -1;
        }
        int i = 0;
        int j = 0;
        while (i < n - m + 1) {
            // 找到首字母相等
            while (i < n && haystack.charAt(i) != needle.charAt(j)) {
                i++;
            }
            if (i == n) {// 没有首字母相等的
                return -1;
            }
            // 遍历后续字符,判断是否相等
            i++;
            j++;
            while (i < n && j < m && haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            }
            if (j == m) {// 找到
                return i - j;
                i -= j - 1;
                j = 0;
            }
        }
        return -1;
    }
}
// next数组
class Solution {
    public void getNext(int[] next, String s){
        int j = -1;
        next[0] = j;
        for (int i = 1; i<s.length(); i++){
            while(j>=0 && s.charAt(i) != s.charAt(j+1)){
                j=next[j];
            }
            if(s.charAt(i)==s.charAt(j+1)){
                j++;
            }
            next[i] = j;
        }
    }

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

重复的子字符串

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

示例 1:

输入: “abab”

输出: True

解释: 可由子字符串 “ab” 重复两次构成。

这又是一道标准的KMP的题目。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        if (s.equals("")) return false;
        int len = s.length();
        // 原串加个空格(哨兵),使下标从1开始,这样j从0开始,也不用初始化了
        s = " " + s;
        char[] chars = s.toCharArray();
        int[] next = new int[len + 1];
        // 构造 next 数组过程,j从0开始(空格),i从2开始
        for (int i = 2, j = 0; i <= len; i++) {
            // 匹配不成功,j回到前一位置 next 数组所对应的值
            while (j > 0 && chars[i] != chars[j + 1]) j = next[j];
            // 匹配成功,j往后移
            if (chars[i] == chars[j + 1]) j++;
            // 更新 next 数组的值
            next[i] = j;
        }
        // 最后判断是否是重复的子字符串,这里 next[len] 即代表next数组末尾的值
        if (next[len] > 0 && len % (len - next[len]) == 0) {
            return true;
        }
        return false;
    }
}

原文创作:ML李嘉图

原文链接:https://www.cnblogs.com/zwtblog/p/15253844.html

文章列表

更多推荐

更多
  • 面试AI技术内参-031经典搜索核心算法:TF 031 经典搜索核心算法:TF-IDF及其变种先来介绍TF-IDF算法。 在信息检索(Information Retrieval)、文本挖掘(Text Mining)以及自然语言处理(Natural Language Processi
  • 面试AI技术内参-004精读2017年EMNLP最佳长论文之一 004 精读2017年EMNLP最佳长论文之一irical Methods in Natural Language Processing),是由国际计算语言学协会**ACL** (Association for Computationa
  • 面试AI技术内参-126复盘5计算机视觉核心技术模块 126复盘 5 计算机视觉核心技术模块 复盘 5 计算机视觉核心技术模块 今模块里,我们一起学习了12期内容,讨论了四个话题,这些话题主要围绕计算机视觉的基础知识和深度学习技术在这个领域的应用。 之所以这么安排,是因为没有深度学
  • 面试AI技术内参-037查询关键字理解三部曲之分类 037 查询关键字理解三部曲之分类技术和基于机器学习的排序算法(Learning to Rank)。 经典的信息检索技术为2000年之前的搜索引擎提供了基本的算法支持。从中衍生出的TF-IDF、BM25还有语言模型(Language
  • 面试AI技术内参-019SIGIR2018论文精读:偏差和流行度之间的关系 019 SIGIR 2018论文精读:偏差和流行度之间的关系2日在美国密歇根州的安娜堡举行。从今天开始,我将精选几篇大会上最有价值的论文,和你一起来读。 我先简单介绍一下这个大会。SIGIR从1978年开始举办,有40年的历史,是信息
  • 面试AI技术内参-022CVPR2018论文精读:如何研究计算机视觉任务之间的关系? 022 CVPR 2018论文精读:如何研究计算机视觉任务之间的关系?PR(Conference on Computer Vision and Pattern Recognition),在美国的盐湖城举行。CVPR大会从1985年开始举
  • 面试AI技术内参-021SIGIR2018论文精读:如何对搜索页面上的点击行为进行序列建模? 021 SIGIR 2018论文精读:如何对搜索页面上的点击行为进行序列建模? 我们已经分享了SIGIR 2018的最佳论文,介绍了如何对推荐系统中的偏差进行建模,从而能够利用这种对偏差的理解,来更加准确地对待基于流行度的推荐结果。周
  • 面试AI技术内参-024CVPR2018论文精读:如何解决排序学习计算复杂度高这个问题? 024 CVPR 2018论文精读:如何解决排序学习计算复杂度高这个问题?于排序的损失函数的有效优化》(Efficient Optimization for Rank-based Loss Functions)。 还是先简单介绍下论文
  • 面试AI技术内参-061基于隐变量的模型之一:矩阵分解 061 基于隐变量的模型之一:矩阵分解 -内容特征的推荐模型。 这周,我们来看一类非常重要的推荐模型:**基于隐变量的推荐模型**。这类模型的优势是对用户和物品信息中的隐含结构进行建模,从而能够挖掘更加深层次的用户和物品关系。 什么
  • 面试AI技术内参-107基于门机制的RNN架构:LSTM与GRU 107 基于门机制的RNN架构:LSTM与GRU -地利用了文字的序列信息,从而能够对文本进行大规模的建模。在上一次的分享里,我们聊了对序列建模的深度学习利器"递归神经网络",或简称RNN。我们分析了文本信息中的序列数据,了解了如何对文
  • 近期文章

    更多
    文章目录

      推荐作者

      更多