String Notes

update Jan 10, 2018 20:16

概述

String 的常见问题可以归纳为如下几类：

Char Removal
De-duplication
replace
Reversal (swap)
Substring
shuffling
Permutation
Decoding/Encoding
DP, longest substring
matching

1. Char Removal

    input：  ____aaa___bb_cc__
    output: aaa_bb_cc

    即去掉input string的首位空格，并且每个词之前只保留一个空格。

基本思想是使用 two-pointers 的方法，i 和 j 分别对应左右指针。维持已经筛选过的部分在 i 的左边(i指向最后一个位置)，用 j 一路向右扫描，需要更新的时候就把需要的字符赋值给 ++i；
Java Code:

    public class Solution {
      public String removeSpaces(String input) {
        char[] arr = input.toCharArray();
        int i = -1, j = 0;
        // 如果见到单词，则设为true，如果见到空格且flag为true，表示刚离开单词，补空格
        boolean flag = false;
        for (j = 0; j < arr.length; ++j) {
          if (arr[j] != ' ') {
            flag = true;
            arr[++i] = arr[j];
          } else if (flag) {
            // 刚离开一个单词
            arr[++i] = ' ';
            flag = false;
          }
        }
        if (i == -1) return "";
        StringBuilder sb = new StringBuilder();
        // 如果input以空格结尾，此时 i 指向最后一个多余空格，否则指向最后一个字母
        for (int k = 0; k <= i; ++k) {
          sb.append(arr[k]);
        }
        if (sb.charAt(sb.length() - 1) == ' ') sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
      }
    }

2. De-duplicate

    (1)
      input:  aaa_bb_cc
      return: a_b_c

还是two pointers。

    (2)
      input:  abbacd
      output: cd

      即重复串消除之后，如果左右部分合并生成了新的重复串，继续消除

用 stack。

Java Code:

  public class Solution {
    public String deDup(String input) {
      Deque<Character> stack = new ArrayDeque<>();
      int idx = 0;
      boolean dup = false;
      while (idx < input.length()) {
        if (stack.isEmpty()) {
          stack.offerLast(input.charAt(idx++));
        } else if (stack.peekLast() == input.charAt(idx)) {
          idx++;
          dup = true;
        } else {
            if (dup) {
            stack.pollLast();
            dup = false;
          } else {
            stack.offerLast(input.charAt(idx++));
          }
        }
      }
      if (dup) {
        stack.pollLast();
      }
      StringBuilder sb = new StringBuilder();
      for (char c : stack) {
        sb.append(c);
      }
      return sb.toString();
    }
  }

  (3). Remove Spaces, delete leading/trailing/duplicated spaces
       “  a” --> “a”
       “   I     love MTV   ” --> “I love MTV”

基本思路是在每个单词结束之后插入一个space，跳过所有space，最后再检查删除头尾的space；

Java Code：

  public class Solution {
    public String removeSpaces(String input) {
      StringBuilder sb = new StringBuilder();
      boolean space = false;
      char[] arr = input.toCharArray();
      // pass all spaces, add a space after each word
      for (char c : arr) {
        if (c == ' ') {
          space = true;
          continue;
        } else {
          if (space) {
            sb.append(" ");
            space = false;
          }
          sb.append(c);
        }
      }
      // delete leading/trailing space
      if (sb.length() == 0) return "";
      if (sb.charAt(0) == ' ') {
        sb.deleteCharAt(0);
      }
      if (sb.charAt(sb.length() - 1) == ' ') {
        sb.deleteCharAt(sb.length() - 1);
      }
      return sb.toString();
    }
  }

3. Str-str

经典题目，求一个string是否是另一个string的substring。基本方法是 O(len(small string)^2) 的时间复杂度，还有 KMP 和 Robin Karp 两个常见的 O(n) 时间的实现，但是一般来说不会考实现。

    public class Solution {
      public int strstr(String large, String small) {
        if ("".equals(small)) return 0;
        for (int k = 0; k < large.length(); ++k) {
          int i = 0;
          while (i < small.length() && k + i < large.length()) {
            if (large.charAt(k + i) != small.charAt(i)) break;
            i++;
          }
          if (i == small.length()) return k;
        }
        return -1;
      }
    }

4. Replacement

    Assumptions

    input, S and T are not null, S is not empty string
    Examples

    input = "appledogapple", S = "apple", T = "cat", input becomes "catdogcat"
    input = "dodododo", S = "dod", T = "a", input becomes "aoao"

用一个指针扫描input string，用一个StringBuilder保存结果，每次发现接下来的部分和 S match后，就append T，指针跳过len(S)个位置，否则的话就append当前字符，指针右移一位。

    public class Solution {
      public String replace(String input, String s, String t) {
        int r = 0;
        StringBuilder sb = new StringBuilder();
        while (r < input.length()) {
          if (match(input, s, r)) {
            sb.append(t);
            r += s.length();
          } else {
            sb.append(input.charAt(r++));
          }
        }
        return sb.toString();
      }
      private boolean match(String input, String s, int start) {
        if (start + s.length() - 1 >= input.length()) return false;
        int i = 0;
        while (i < s.length()) {
          if (input.charAt(start + i) != s.charAt(i)) return false;
          i++;
        }
        return true;
      }
    }

5. Decoding-Encoding, Compress

LeetCode: String Compression
整体思路是扫描input string，每次检查当前字母连续重复个数，然后相应inplace地去重新赋值。具体地，维持 l 和 r 两个指针，l 指向要返回的结果的最后一个位置，r 作为探测指针向右扫描。详见下面的comments。

    class Solution {
        public int compress(char[] chars) {
            int l = -1, r = 0;
            while (r < chars.length) {
                int num = count(chars, r);
                chars[++l] = chars[r]; // 先复制字母，然后添加数字
                if (num > 1) {
                    // 从 l+1 开始添加数字，并且更新l的值，为数字最后一位的index
                    l = insertNumber(chars, l + 1, num);
                }
                r += num;
            }
            return l + 1;
        }

        // insert given number in chars at start, return new left pointer
        private int insertNumber(char[] chars, int start, int num) {
            String numString = String.valueOf(num);
            for (int i = 0; i < numString.length(); ++i) {
                chars[start + i] = numString.charAt(i);
            }
            return start + numString.length() - 1;
        }

        // 返回连续出现的个数
        private int count(char[] chars, int start) {
            int ret = 1;
            char c = chars[start];
            start += 1;
            while (start < chars.length) {
                if (chars[start++] == c) ret++;
                else break;
            }
            return ret;
        }
    }

6. Reversal

1, LeetCode: Reverse String
两种方法，iterative 或者 recursion。 2, LeetCode: Reverse Words in a String
稍微复杂，解答见笔记

7. Shuffling

    input:  ABCDE12345
    output: A1B2C3D4E5

8. Sliding window

解决需要在窗口中维持一种变量，并且这种变量可以根据窗口边界元素的进出进行更新的问题。例如

找s1中全部的s2的同分异构串；
找最长的仅包含unique characters 的 substring；
对于一个只含有 0 和 1 的字符串，最多反转 k 个 0，求可以生成的最长全是 1 的子串；

String Notes

String Notes

概述

1. Char Removal

2. De-duplicate

5. Decoding-Encoding, Compress

6. Reversal

7. Shuffling

8. Sliding window

results matching ""

No results matching ""