## 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.

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;

}

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