“Finger Offer 05. Replace space – 58. Rotate string left”

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Topic describes
1. Replace Spaces (level is simple)

Implement a function that replaces each space in the string s with “%20”.

The sample

Enter: s ="We are happy."Output:"We%20are%20happy."
Copy the code
2. Left-rotate string (level simple)

Left-rotation of a string moves several characters from the beginning to the end of the string. Define a function to rotate the string left. For example, if you enter the string “abcdefg” and the number 2, the function will return “cdefgab” as a result of the left rotation.

Example 1

Enter: s ="abcdefg", k = 2Output:"cdefgab"
Copy the code

Example 2

Enter: s ="lrloseumgh", k = 6Output:"umghlrlose"
Copy the code

(1).

1. Replace Spaces

At first look at this problem, almost give oneself complete meng. Use of the replace function, which comes with Java, is not allowed. A single line of code would do the job. But the probability of actually encountering this question in an interview should be extremely low. If you do, you probably won’t be using the replace function directly, but it’s better to think of another way than not writing at all. To be clear: Strings are immutable types in Java and cannot be manipulated in place. You can build A StringBuilder to manipulate a new string and return the result.

2. Code implementation (Clever method)
class Solution {
    public String replaceSpace(String s) {
        if (s == null) {
            return null;
        }
        return s.replace(""."% 20"); }}Copy the code
3. Code implementation (StringBuilder replacement)
class Solution {
  public String replaceSpace(String s) {
    if (null == s) {
      return null;
    }
    StringBuilder result = new StringBuilder();
    for (char c : s.toCharArray()) {
      if (' ' == c) {
        result.append("% 20");
      } else{ result.append(c); }}returnresult.toString(); }}Copy the code

Consider using char instead of Character to avoid boxing time as you loop through the string here.

Time complexity O(N) : Traverses the entire string, linear relationship.

Spatial complexity O(N) : Strings in Java are designed to be immutable types. A new StringBuilder takes up linear space and is length dependent.

Analysis of ideas (left rotation string)

As in the previous problem, direct cutting + splicing can get the result immediately, but on second thought, it seems that things are not so simple.

1. The analysis

It is not explicitly stated that slicing can’t be used, so I wrote both solutions to be on the safe side and used StringBuilder to concatenate strings.

2. Code implementation (sub cutting)
class Solution {
  public String reverseLeftWords(String s, int n) {
    if (null == s) {
      return null;
    }
    if (n + 1 > s.length()) {
      return s;
    }
    return s.substring(n) + s.substring(0, n); }}Copy the code
3. Code implementation (traversal string +StringBuilder concatenation)

Before solving the problem, it is necessary to familiarize yourself with the remainder % operation in Java.

class Solution {
  public String reverseLeftWords(String s, int n) {
    if (null == s) {
      return null;
    }
    StringBuilder res = new StringBuilder();
    for (int i = n; i < n + s.length(); i++) {
      res.append(s.charAt(i % s.length()));
    }
    returnres.toString(); }}Copy the code

The remainder is done here just to keep the code simple

The complexity of the

Time complexity O(N) : requires traversal of the entire string, linear relationship.

Space complexity O(N) : Auxiliary StringBuilder, space complexity is linear to string length.

link

Replace the blank space

Left rotation string