Created
September 7, 2019 23:22
-
-
Save saketj/b11d3986dacd2bd530a50fc315ed49b5 to your computer and use it in GitHub Desktop.
Q1 Strings: Remove exactly one character to make strings equal
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.io.*; | |
| import java.lang.*; | |
| import java.util.*; | |
| public class Q1Strings { | |
| public static boolean equalsWhenOneCharRemoved(String x, String y) { | |
| // Time complexity: O(N) | |
| // Space complexity: O(1) | |
| int diff = 0; | |
| int m = x.length(); | |
| int n = y.length(); | |
| // x and y should differ by exactly 1 in length. | |
| // If they do not differ in length by 1, then return false directly. | |
| if (Math.abs(m - n) != 1) return false; | |
| if (m < n) { | |
| // We will iterate over the larger string. | |
| // To make the first argument larger, we call this function again | |
| // if the x is smaller in length than y. | |
| return equalsWhenOneCharRemoved(y, x); | |
| } | |
| // If here, it is guaranteed that len(x) - len(y) == 1 | |
| // Iterate over the larger string and compare character by character | |
| // and count the diffs. | |
| for (int i = 0; i < x.length(); ++i) { | |
| char x_ch = x.charAt(i); | |
| char y_ch = (i < y.length()) ? y.charAt(i) : ' '; | |
| if (x_ch != y_ch) { | |
| ++diff; | |
| } | |
| } | |
| if (diff == 1) return true; | |
| return false; | |
| } | |
| public static void main(String args[]) { | |
| // Couple of test cases: | |
| assert(equalsWhenOneCharRemoved("x", "y") == false); | |
| assert(equalsWhenOneCharRemoved("x", "XX") == false); | |
| assert(equalsWhenOneCharRemoved("yy", "yx") == false); | |
| assert(equalsWhenOneCharRemoved("abcd", "abxcd") == true); | |
| assert(equalsWhenOneCharRemoved("xyz", "xz") == true); | |
| System.out.println("All test cases passed."); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment