Given an original string input, and two strings S and T, replace all occurrences of S in input with T.

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"

Solution:

类似string match，当input.charAt(i + j) != s.charAt(j)时，append input.charAt(i)，当match时，则append t，并更新i。注意t = ""时，还有不要忘记i > input.length() - s.length()时要append剩下的字母

  public String replace(String input, String s, String t) {

    if (input.length() == 0 || s.length() == 0) {
      return input;
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < input.length(); i++) {  //注意不是i <= input.length() - s.length()
      if (i > input.length() - s.length()) {
        sb.append(input.charAt(i));
        continue;
      }
      for (int j = 0; j < s.length(); j++) {
        if (input.charAt(i + j) != s.charAt(j)) {
          sb.append(input.charAt(i));
          break;
        }
        if (j == s.length() - 1) {
          sb.append(t);
          i = i + j;
        }
      }
    }
    return sb.toString();
  }