LeetCode Day7 String Part.1
Tags: leetcode, java, algorithms
Published: 2024-06-13 14:37:32

## LeetCode No.344 Reverse String
Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

 

Example 1:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Example 2:

Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]
 

Constraints:

1 <= s.length <= 105
s[i] is a printable ascii character.

[Original Page](https://leetcode.com/problems/reverse-string/description/)

A very traditional method about double vector (left-right-double vector)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/26vccaie7pk1nsqfpj6t.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7e8a8r1pva1j7aoyrhx6.png)
```
    public void reverseString(char[] s) {
        if(s==null || s.length ==0){
            return;
        }

        int left = 0;
        int right = s.length-1;

        while(left < right){
            char temp = s[left];
            s[left++] = s[right];
            s[right--] = temp;
        }
    }
```



## LeetCode No. 541 Reverse String II

Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.

If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and leave the other as original.

 

Example 1:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"
Example 2:

Input: s = "abcd", k = 2
Output: "bacd"
 

Constraints:

1 <= s.length <= 104
s consists of only lowercase English letters.
1 <= k <= 104

```
    public String reverseStr(String s, int k) {
        char[] arr = s.toCharArray();
        int index = 0;
        while(index < arr.length){
            if(index+k-1 >= arr.length){
                reverse(index, arr.length-1,arr);
                index += k-1;
            }
            else{
                reverse(index,index+k-1,arr);
                index += 2*k;
            } 
        }
        return new String(arr);
    }

    public void reverse(int left, int right, char[] arr){
        if(arr == null || arr.length==0){
            return;
        }
        while(left < right){
            char temp = arr[left];
            arr[left++] = arr[right];
            arr[right--] = temp;
        }
    }
```
The only difference from the No.344 Reverse String is here we need to evaluate the k target.
Time: O(n) (O(n/k)for while loop and O(k)for inner loop so O(n)for total )
Space: O(n) because we need arr[]


---
## KamaCoder No.54 Replace Number

Topic Description.
Given a string s that contains lowercase alphabetic and numeric characters, write a function that leaves the alphabetic characters in the string unchanged and replaces each numeric character with a number. For example, for the input string "a1b2c3", the function should convert it to "anumberbnumbercnumber".

Input Description
Input a string s,s containing only lowercase letters and numeric characters.

Output Description
Print a new string where each numeric character is replaced with number

Input Example
a1b2c3

Output Example
anumberbnumbercnumber

Hints
Data range:
1 <= s.length < 10000.

Translated with DeepL.com (free version)


```
    public static void main (String[] args) {
    Scanner scanner = new Scanner(System.in);
    
    String s = scanner.nextLine();
    char[] arr = s.toCharArray();
    StringBuffer sb = new StringBuffer();
    for(int i=0; i<arr.length; i++){
        if('0'<=arr[i]&& arr[i] <='9'){
            sb.append("number");
        }else{
            sb.append(arr[i]);
        }
        
    }
    System.out.println(sb.toString());
    /* code */

}
```
Time: O(n), Space: O(n) for char[] and Buffer

Here we can improve if 

```
public class Main{
    public static void main (String[] args) {
    Scanner scanner = new Scanner(System.in);
    
    String s = scanner.nextLine();
    scanner.close();
    int count = 0;
    
    
    for(int i=0; i<s.length();i++){
        if(s.charAt(i)<='9' && s.charAt(i)>='0'){
            count++;
        }
    }
    
    char[] arr = new char[count * 5 + s.length()];
    
    System.arraycopy(s.toCharArray(), 0, arr, 0, s.length());
    
    int left = s.length()-1;
    int right = arr.length-1;
    
    while(left >-1){
        if(Character.isDigit(arr[left])){
            arr[right--] = 'r';
            arr[right--] = 'e';
            arr[right--] = 'b';
            arr[right--] = 'm';
            arr[right--] = 'u';
            arr[right--] = 'n';
            left--;
            
        }else{
            arr[right--] = arr[left--]; 
        }
    }

    System.out.println(new String(arr));
    /* code */

    }
}
```
Only use char[]