Handling String Problems

Topic 4: Replacement of Spaces

Title Description:

Please implement a function that replaces each space in the string with "% 20". For example, enter "We are happy." and output "We% 20 are% 20 happy.".

Algorithmic ideas:

1. If a space is scanned each time and replaced by% 20, the array will be shifted backwards after each replacement (O(n^2)).

2. Traverse the array first and count the total number of spaces in the string. Each space is replaced by a space, and the length of the replaced string increases by 2. Therefore, the length of the replaced string is equal to the original length plus 2 times the number of spaces. All characters are moved only once, and the time complexity is O(n).

code implementation

package swordToOffer;

public class Num4_ReplaceBlank {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		StringBuffer s = null;
		String result = RepalceBlank(s);
		System.out.println(result);
		StringBuffer s1 = new StringBuffer("ab2s4");
		result = RepalceBlank(s1);
		System.out.println(result);
		StringBuffer s2 = new StringBuffer("a b45 dd");
		result = RepalceBlank(s2);
		System.out.println(result);
		StringBuffer s3 = new StringBuffer("");
		result = RepalceBlank(s3);
		System.out.println(result);
	}

	//StringBuffer - Thread Safe StringBuilder - Non-Thread Safe Length Variable 
	public static String RepalceBlank(StringBuffer str) {
		if(str==null) {
			System.out.println("input is null");
			return null;
		}
		
		int originalLength = str.length();
		int numberOfBlank = 0;
		//int i=0;
		for(int i=0;i<str.length();i++) {
			//originalLength++;
			if(str.charAt(i)==' ') {
				numberOfBlank++;
			}
		}
		
		int newLength = originalLength+numberOfBlank*2;
		//if(newLength==str.length()) return str.toString();
		str.setLength(newLength);
		int indexOfOriginal = originalLength-1;//There will be spillovers
		int indexOfNew = newLength-1;//
		
		while(indexOfOriginal>=0&&indexOfNew>indexOfOriginal) {
			if(str.charAt(indexOfOriginal)==' ') {
				str.setCharAt(indexOfNew--, '0');
				str.setCharAt(indexOfNew--, '2');
				str.setCharAt(indexOfNew--, '%');
			}else {
				str.setCharAt(indexOfNew--,str.charAt(indexOfOriginal));
			}
			indexOfOriginal--;
		}
		return str.toString();
	}
}

Output results:

input is null
null
ab2s4
a%20b45%20dd

Analysis:

If you encounter data replacement or need to move multiple times, you can consider moving backwards and forwards to reduce the number of moves.

Time Complexity O(n) Space Complexity O(1)