Day15——字符串专题

╰+哭是因爲堅強的太久メ 2024-04-01 09:20 77阅读 0赞

#### 文章目录 ####

*   *   *  33.翻转字符串里的单词
         *  34.实现 \`strStr()\`

--------------------

#### 33.翻转字符串里的单词 ####

**解题思路：**

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

**例子：**

*  源字符串为："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;
            }
        }
    }

#### 34.实现 `strStr()` ####

**思路**：**前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配，注意字符串的**前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串\*\*；**后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串**\*\*

**代码实现：**

class Solution {
        
        //前缀表（不减一）Java实现
        public int strStr(String haystack, String needle) {
        
            if (needle.length() == 0) return 0;
            int[] next = new int[needle.length()];
            getNext(next, needle);
    
            int j = 0;
            for (int i = 0; i < haystack.length(); i++) {
        
                while (j > 0 && needle.charAt(j) != haystack.charAt(i)) 
                    j = next[j - 1];
                if (needle.charAt(j) == haystack.charAt(i)) 
                    j++;
                if (j == needle.length()) 
                    return i - needle.length() + 1;
            }
            return -1;
    
        }
        
        private void getNext(int[] next, String s) {
        
            int j = 0;
            next[0] = 0;
            for (int i = 1; i < s.length(); i++) {
        
                while (j > 0 && s.charAt(j) != s.charAt(i)) 
                    j = next[j - 1];
                if (s.charAt(j) == s.charAt(i)) 
                    j++;
                next[i] = j; 
            }
        }
    }