Sunday, April 11, 2010

CodingBat string manipulation problems - Part 5

This last part covers some solutions that aren't pure regex; unlike the other parts where I used stubbornly used regex whenever possible, here I use whatever comes naturally.

xyBalance: Return true if the given string is xy-balanced, that is for all the 'x' chars in the string, there exists a 'y' char somewhere later in the string. One 'y' can balance multiple 'x's.
public boolean xyBalance(String str) {
  return str.lastIndexOf('x') <= str.lastIndexOf('y');
}
Alternate regex solution:
public boolean xyBalance(String str) {
  return str.matches("(.*y)?[^x]*");
}

xyzMiddle: Given a string, does "xyz" appear in the middle of the string? To define middle, we'll say that the number of chars to the left and right of the "xyz" must differ by at most one.
public boolean xyzMiddle(String str) {
  int p = (str.length() - 3) / 2;
  return (p >= 0) && str.substring(p, str.length() - p).matches(".?xyz.?");
}

endOther: Given two strings, return true if either of the strings appears at the very end of the other string, ignoring upper/lower case differences.
public boolean endOther(String a, String b) {
  return a.length() < b.length() ? endOther(b, a)
    : a.toLowerCase().endsWith(b.toLowerCase());
}

sumNumbers: Given a string, return the sum of the numbers appearing in the string, ignoring all other characters.
public int sumNumbers(String str) {
  int sum = 0;
  for (String number : (0 + str).split("\\D+")) {
    sum += Integer.parseInt(number);
  }
  return sum;
}
Prepending "0" is an example of input normalization to eliminate the otherwise exceptional possibility of the first string being empty.
mirrorEnds: Return the longest prefix that in reverse order is a suffix (possibly overlapping).
public String mirrorEnds(String str) {
  for (int i = 0, L = str.length(); i < L; i++) {
    if (str.charAt(i) != str.charAt(L - 1 - i)) {
      return str.substring(0, i);
    }
  }
  return str;
}

Recursions

mixString: Given two strings, A and B, create a bigger string made of the first char of A, the first char of B, the second char of A, the second char of B, and so on. Any leftover chars go at the end of the result.
public String mixString(String a, String b) {
  return 
    a.isEmpty() ? b :
    b.isEmpty() ? a :
    a.substring(0, 1) + b.substring(0, 1)
      + mixString(a.substring(1), b.substring(1));
}

repeatSeparator: Given two strings, word and a separator, return a big string made of count occurrences of word, separated by sep.
public String repeatSeparator(String word, String sep, int count) {
  return
    count == 0 ? "" :
    count == 1 ? word :
    word + sep + repeatSeparator(word, sep, count - 1);
}

repeatFront: Given a string and an int n, return a string made of the first n characters of the string, followed by the first n-1 characters of the string, and so on. You may assume that n is between 0 and the length of the string, inclusive.
public String repeatFront(String str, int n) {
  return (n == 0) ? ""
    : str.substring(0, n) + repeatFront(str, n - 1);
}

maxBlock: Given a string, return the length of the largest "block" in the string. A block is a run of adjacent chars that are the same.
public int maxBlock(String str) {
  int N;
  return str.isEmpty() ? 0
    : Math.max(
        N = str.replaceAll("(.)(\\1*).*", "$1$2").length(),
        maxBlock(str.substring(N))
      );
}

plusOut: Given a string and a non-empty word string, return a version of the original string where all chars have been replaced by pluses ("+"), except for appearances of the word string which are preserved unchanged.
public String plusOut(String str, String word) {
  int i = str.indexOf(word);
  return i == -1 ? str.replaceAll(".", "+")
    : str.substring(0, i).replaceAll(".", "+") +
        word + plusOut(str.substring(i + word.length()), word);
}
This doesn't handle overlappping word occurrences. See also: regex solution in Extra.

2 comments:

  1. public int sumDigits(String str) {
    int ans=0;
    for(int i = 0; i<str.length(); i++)
    {
    if(Character.isDigit(str.charAt(i)))
    ans+=Integer.parseInt(str.substring(i,
    i+1)); // I got cut off by Y! Answers there
    }
    return ans;

    }

    ReplyDelete
  2. public int sumDigits(String str) {
    int sum = 0;
    for (int ch : str.replaceAll("\\D+", "").toCharArray()) {
    sum += Character.digit(ch, 10);
    }
    return sum;
    }

    ReplyDelete