3 min read•Last Updated on June 18, 2024
Avanish Gupta
Milo Chang
Avanish Gupta
Milo Chang
Using for loops, we can also develop many useful algorithms with Strings. There are several that you need to know in this course. The focus of this topic is on developing algorithms using Strings. (For more information about the String methods that you should know for the exam, you can visit this guide!)
If you ever have issues understanding or writing an algorithm that works with Strings, it helps to use a short String (like "house") to test what the algorithm actually does. You can use scratch paper to trace the indices and see every step of the algorithm.
To reverse a string, we need to go get the first character and make it into a String. Then we get the 2nd character and put it before the first character. Then we repeat until all the characters are used up.
public static String reverse(String s) {
String result = ""
for (int i = 0; i < string.length(); i++) {
result = s.substring(i,i+1) + result;
}
return result;
}
This can be used to print all characters in the string by setting the length n to 1. To get longer substrings, we increase n to the length of the substrings you want to find. This value can be up to the length of the overall string itself, but no more. This would create an exception.
How this algorithm works is similar to a sliding window. The beginning of the window is at the beginning of the substring you want to print and the end of the window is the end of the substring. Therefore the width of the rectangle is n.
We first set the window to start at the beginning of the string. This corresponds to the loop initialization. Then, the window slides to the right by one character every iteration to represent the loop increment. The loop stops when the end of the window reaches the end of the string.
To achieve this, we need the beginning of the window to be less than the length of the string + 1 - n.
public static void printSubstringsLengthN(String s, int n) {
for (int i = 0; i < (s.length() + 1 - n); i++) {
System.out.println(s.substring(i, i+n));
}
}
We can easily adapt the method above to check if there are any substrings in an input String that consist of a desired sequence of characters.
Calling the method below with checkForSubstring("house", "us"); would return true while checkForSubstring("bob", "us"); would return false.
public static boolean checkForSubstring(String s, String n) {
for (int i = 0; i < (s.length() + 1 - n.length()); i++) {
String currentSubString = (s.substring(i, i+n.length()));
if (currentSubString.equals(n)) {
return true;
}
}
return false;
}
We can also adapt the methods we have used so far to count the number of substrings in an input String that meet a certain criteria.
Calling the method below with countSubstrings("banana", "a"); will return the number of times the letter "a" is in the word "banana," which is 3 in this case. We can also call countSubstrings("ABBBAABBAABBABAB", "ABBA"); which will return the number of times "ABBA" is in the input String, which in this case is 2.
public static int countSubstrings(String s, String n) {
int count = 0;
for (int i = 0; i < (s.length() + 1 - n.length()); i++) {
String currentSubString = (s.substring(i, i+n.length()));
if (currentSubString.equals(n)) {
count++;
}
}
return count;
}
The equals method is a method in Java that is used to compare two objects for equality. It checks if the values of the objects are the same, rather than comparing their memory addresses.
Term 1 of 6
The equals method is a method in Java that is used to compare two objects for equality. It checks if the values of the objects are the same, rather than comparing their memory addresses.
Term 1 of 6
The equals method is a method in Java that is used to compare two objects for equality. It checks if the values of the objects are the same, rather than comparing their memory addresses.
Term 1 of 6
Reversing a string means to change the order of its characters, so that the last character becomes the first, the second-to-last becomes the second, and so on.
Substring: A substring is a smaller part of a larger string. It can be obtained by extracting characters from within the original string.
Length: The length of a string refers to the number of characters it contains.
Concatenation: Concatenation is combining two or more strings together to create a new string.
A sliding window is a technique used in computer science and algorithms where a fixed-size window moves through an array or string to perform operations on subarrays or substrings. It allows for efficient processing of data by avoiding redundant calculations.
Two Pointers: This term refers to using two pointers, usually starting from both ends, to traverse an array or list simultaneously.
Prefix Sum Array: This term refers to an array where each element represents the sum of all elements before it in another given array.
Dynamic Programming: This term refers to solving complex problems by breaking them down into simpler overlapping subproblems and storing their solutions for future use.
Loop initialization is the step in programming where variables are assigned initial values before entering a loop. It sets up the starting conditions for the loop's execution.
Loop Condition: This term refers to the condition that must be true for a loop to continue executing.
Loop Termination: This term refers to the condition that causes a loop to stop executing and exit.
Nested Loops: This term refers to loops within loops, where one loop is contained inside another loop.
Loop increment is the step in programming where variables are updated or modified after each iteration of a loop. It determines how the loop progresses and when it will eventually terminate.
Loop Decrement: This term refers to decreasing the value of a variable after each iteration of a loop.
Loop Control Variable: This term refers to the variable that is modified during each iteration of a loop to control its execution.
Infinite Loop: This term refers to a loop that continues indefinitely without ever terminating.