Strings Flashcards
Is String Palindromic Time O(n) Space O(1)
public static boolean isPalindromic(String s) { for (int i = 0, j = s.length() - 1; i < j; ++i, –j) { if (s.charAt(i) != s.charAt(j)) { return false; } } return true; }
Implement an integer to string conversion function and a string to integer conversion function.
public static String intToString(int x) { boolean isNegative = false; if (x < 0) { isNegative = true; } StringBuilder s = new StringBuilder(); do { s.append((char)(‘0’ + Math.abs(x % 10))); x /= 10; } while (x != 0); // Adds the negative sign back if isNegative. return s.append(isNegative ? “-“ : “”).reverse().toString(); } public static int stringToInt(String s) { return (s.charAt(0) == ‘-‘ ? -1 : 1) * s.substring((s.charAt(0) == ‘-‘ || s.charAt(0) == ‘+’) ? 1 : 0) .chars() .reduce(0, (runningSum, c) -> runningSum * 10 + c - ‘0’); }
Write a program that performs base conversion. The input is a string, an integer b1, and another integer b2. The string represents an integer in base b1. The output should be the string representing the integer in base b2. Time: O(n(1 + log_b2 b1)) n is the length of s.
public static String convertBase(String numAsString, int b1, int b2) { boolean isNegative = numAsString.startsWith(“-“); int numAsInt = numAsString.substring(isNegative ? 1 : 0) .chars() .reduce(0, (x, c) -> x * b1 + (Character.isDigit(c) ? c - ‘0’ : c - ‘A’ + 10)); return (isNegative ? “-“ : “”) + (numAsInt == 0 ? “0” : constructFromBase(numAsInt, b2)); }
Implement a function that converts a spreadsheet column id to the corresponding integer, with “A” corresponding to 1. Time O(n)
public static int ssDecodeColID(final String col) { return col.chars().reduce(0, (result, c) -> result * 26 + c - ‘A’ + 1); }
Write a program which takes as input an array of characters, and removes each ‘b’ and replaces each ‘a’ by two ‘d’s. Specifically along with the array, you are provided an integer-valued size. Time O(n) Space O(1)
public static int replaceAndRemove(int size, char[] s) { // Forward iteration: remove “b”s and count the number of “a”s. int writeIdx = 0, aCount = 0; for (int i = 0; i < size; ++i) { if (s[i] != ‘b’) { s[writeIdx++] = s[i]; } if (s[i] == ‘a’) { ++aCount; } } // Backward iteration: replace “a”s with “dd”s starting from the end. int curIdx = writeIdx - 1; writeIdx = writeIdx + aCount - 1; final int finalSize = writeIdx + 1; while (curIdx >= 0) { if (s[curIdx] == ‘a’) { s[writeIdx–] = ‘d’; s[writeIdx–] = ‘d’; } else { s[writeIdx–] = s[curIdx]; } –curIdx; } return finalSize; }
Implement a function which takes as input a string s and returns true if s is a palindromic string. Time O(n)
public static boolean isPalindrome(String s) { // i moves forward, and j moves backward. int i = 0, j = s.length() - 1; while (i < j) { // i and j both skip non-alphanumeric characters. while (!Character.isLetterOrDigit(s.charAt(i)) && i < j) { ++i; } while (!Character.isLetterOrDigit(s.charAt(j)) && i < j) { –j; } if (Character.toLowerCase(s.charAt(i++)) != Character.toLowerCase(s.charAt(j–))) { return false; } } return true; }
Implement a function for reversing the words in a string s. Time O(n) Space O(1)
public static void reverseWords(char[] input) { int n = input.length; // First, reverses the whole string. reverse(input, 0, n - 1); // Second, Reverses each word in the string. int start = 0, finish = 0; while (start < n) { while (start < finish || start < n && input[start] == ‘ ‘) { ++start; // Skip spaces chars. } while (finish < start || finish < n && input[finish] != ‘ ‘) { ++finish; // Skip non-spaces chars. } reverse(input, start, finish - 1); } } private static void reverse(char[] array, int start, int end) { while (start < end) { char tmp = array[start]; array[start++] = array[end]; array[end–] = tmp; } }
Write a program that takes as input an integer n and returns the nth integer in the look-and-say sequence. Return the result as a string. O(n2^n)
public static String lookAndSay(int n) { String s = “1”; for (int i = 1; i < n; ++i) { s = nextNumber(s); } return s; } private static String nextNumber(String s) { StringBuilder result = new StringBuilder(); for (int i = 0; i < s.length(); ++i) { int count = 1; while (i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1)) { ++i; ++count; } result.append(count).append(s.charAt(i)); } return result.toString(); }
Write a program which takes as input a valid Roman number string s and returns the integer it corresponds to. Time O(n)
public static int romanToInteger(String s) { Map T = Map.of(‘I’, 1, ‘V’, 5, ‘X’, 10, ‘L’, 50, ‘C’, 100, ‘D’, 500, ‘M’, 1000); int sum = T.get(s.charAt(s.length() - 1)); for (int i = s.length() - 2; i >= 0; –i) { if (T.get(s.charAt(i)) < T.get(s.charAt(i + 1))) { sum -= T.get(s.charAt(i)); } else { sum += T.get(s.charAt(i)); } } return sum; }
Write a program that determines where to add periods to a decimal string so that the resulting string is a valid IP address. There may be more than one valid IP addresses corresponding to a string in which case you should print all possibilities. IP address is constant (2^32) Time O(1)
public static List getValidIpAddress(String s) { List result = new ArrayList<>(); for (int i = 1; i < 4 && i < s.length(); ++i) { final String first = s.substring(0, i); if (isValidPart(first)) { for (int j = 1; i + j < s.length() && j < 4; ++j) { final String second = s.substring(i, i + j); if (isValidPart(second)) { for (int k = 1; i + j + k < s.length() && k < 4; ++k) { final String third = s.substring(i + j, i + j + k); final String fourth = s.substring(i + j + k); if (isValidPart(third) && isValidPart(fourth)) { result.add(first + “.” + second + “.” + third + “.” + fourth); } } } } } } return result; } private static boolean isValidPart(String s) { if (s.length() > 3) { return false; } // “00”, “000”, “01”, etc. are not valid, but “0” is valid. if (s.startsWith(“0”) && s.length() > 1) { return false; } int val = Integer.parseInt(s); return val <= 255 && val >= 0; }
Write a program which takes as input a string s and returns the snakestring of s.
public static String snakeString(String s) { StringBuilder result = new StringBuilder(); // Outputs the first row, i.e., s[1], s[5], s[9], … for (int i = 1; i < s.length(); i += 4) { result.append(s.charAt(i)); } // Outputs the second row, i.e., s[0], s[2], s[4], … for (int i = 0; i < s.length(); i += 2) { result.append(s.charAt(i)); } // Outputs the third row, i.e., s[3], s[7], s[11], … for (int i = 3; i < s.length(); i += 4) { result.append(s.charAt(i)); } return result.toString(); }
Implement run-length encoding and decoding functions. Assume the string to be encoded consists of letters of the alphabet, with no digits, and the string to be decoded is a valid encoding.
public static String decoding(String s) { int count = 0; StringBuilder result = new StringBuilder(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (Character.isDigit(c)) { count = count * 10 + c - ‘0’; } else { // c is a letter of alphabet. while (count > 0) { // Appends count copies of c to result. result.append(c); count–; } } } return result.toString(); } public static String encoding(String s) { int count = 1; StringBuilder ss = new StringBuilder(); for (int i = 1; i <= s.length(); ++i) { if (i == s.length() || s.charAt(i) != s.charAt(i - 1)) { // Found new character so write the count of previous character. ss.append(count).append(s.charAt(i - 1)); count = 1; } else { // s.charAt(i) == s.charAt(i - 1). ++count; } } return ss.toString(); }
Given two strings s(the “search string”) and t (the “text”), find the first occurrence of s in t. Time O(m + n) m, the length of s and n, the length of t.
// Returns the index of the first character of the substring if found, -1 // otherwise. public static int rabinKarp(String t, String s) { if (s.length() > t.length()) { return -1; // s is not a substring of t. } final int BASE = 26; int tHash = 0, sHash = 0; // Hash codes for the substring of t and s. int powerS = 1; // BASE^|s-1|. for (int i = 0; i < s.length(); i++) { powerS = i > 0 ? powerS * BASE : 1; tHash = tHash * BASE + t.charAt(i); sHash = sHash * BASE + s.charAt(i); } for (int i = s.length(); i < t.length(); i++) { // Checks the two substrings are actually equal or not, to protect // against hash collision. if (tHash == sHash && t.substring(i - s.length(), i).equals(s)) { return i - s.length(); // Found a match. } // Uses rolling hash to compute the new hash code. tHash -= t.charAt(i - s.length()) * powerS; tHash = tHash * BASE + t.charAt(i); } // Tries to match s and t.substring(t.length() - s.length()). if (tHash == sHash && t.substring(t.length() - s.length()).equals(s)) { return t.length() - s.length(); } return -1; // s is not a substring of t. }
