2.10 Implementing String Algorithms

Jump to topic

Unit 2 · Selection and Iteration · Topic 2.10

Implementing String Algorithms

Skill 2.CSkill 3.CSkill 3.D

Big idea: String algorithms loop over indexes, pull out pieces with substring, and test or build strings from those pieces.

Learning objectives

Develop code for standard and original algorithms that involve strings and determine the result of these algorithms.

Reverse a string

Build the result one character at a time. Adding each new character to the front reverses the order.

Code

String word = "stressed";
String rev = "";
for (int i = 0; i < word.length(); i++) {
  rev = word.substring(i, i + 1) + rev;
}
System.out.println(rev);

Output

desserts

Count substrings that meet a condition

To examine every substring of length k, the last start index is length() - k, so the loop condition is i <= s.length() - k.

Code

String s = "abcabcab";
int count = 0;
for (int i = 0; i <= s.length() - 2; i++) {
  if (s.substring(i, i + 2).equals("ab")) {
    count++;
  }
}
System.out.println(count);

Output

Check a property: vowels and palindromes

Code

String w = "racecar";
boolean pal = true;
for (int i = 0; i < w.length() / 2; i++) {
  if (!w.substring(i, i + 1).equals(w.substring(w.length() - 1 - i, w.length() - i))) {
    pal = false;
  }
}
int vowels = 0;
for (int i = 0; i < w.length(); i++) {
  if ("aeiou".indexOf(w.substring(i, i + 1)) >= 0) vowels++;
}
System.out.println(pal + " " + vowels);

Output

true 3

Remove or replace characters

Since strings are immutable, "removing" means building a new string that skips what you don't want, or splicing around a match with indexOf.

Code

String s = "a-b-c-d";
String out = "";
for (int i = 0; i < s.length(); i++) {
  String ch = s.substring(i, i + 1);
  if (!ch.equals("-")) out += ch;
}
System.out.println(out);
String t = "the cat sat";
int at = t.indexOf("cat");
t = t.substring(0, at) + "dog" + t.substring(at + 3);
System.out.println(t);

Output

abcd
the dog sat

Key points

Check whether substrings have a property; count substrings that meet a condition; build a reversed string.
One character at index i: s.substring(i, i + 1).
indexOf returns −1 when there is no match, which is useful as a test.

Watch out

For substrings of length k, the last start index is length() - k. Going further throws an exception.
s.substring(i, i + 1) with i == s.length() throws.

Exam tip

On FRQ Part B (strings), say the algorithm in words first: "for each index, take the next k characters, compare."

Quick check

What prints?

String s = "hello";
String r = "";
for (int i = 0; i < s.length(); i += 2) r += s.substring(i, i + 1);
System.out.println(r);

Show answer

hlo (indexes 0, 2, 4).

Practice 2.10 (12 questions)