public class I4 { /** * Interleaves the characters of two strings by taking one character at a * time, starting with the first string. * e.g "abc" and "defghi" becomes * "adbecfghi". * * Given strings of length N and M, the time complexity is O(N+M) because * the time complexity of the StringBuilder append method is amortized O(1). * So all N+M append operations take O(N+M) time. * * @param s1 the 1st string * @param s2 the 2nd string * @throws IllegalArgumentException if either string missing * @return the new string */ public static String interleave(String s1, String s2) { if( s1 == null || s2 == null ){ throw new IllegalArgumentException(); } StringBuilder s3 = new StringBuilder(s1.length() + s2.length()); // length of the shortest string int minlen = Math.min(s1.length(), s2.length()); for(int i = 0 ; i < minlen ; i++) { s3.append(s1.charAt(i)); s3.append(s2.charAt(i)); } // the longest string String maxstr = s1.length() > s2.length() ? s1 : s2; for(int i = minlen ; i < maxstr.length() ; i++) { s3.append(maxstr.charAt(i)); } return new String(s3); } /** * Interleaves the characters of two strings by taking one character at a * time, starting with the first string. * e.g "abc" and "defghi" becomes * "adbecfghi". * * This implementation uses string concatenation ("+"), which is * inefficient since a new string is created over and over again. * * Given strings of length N and M, the time complexity is O((N+M)^2) * because string concatenation is linear in the length of the strings. * If adding one character at a time, the cost of adding N characters * become become O(1+2+..+N) = O(N^2). * * @param s1 the 1st string * @param s2 the 2nd string * @throws IllegalArgumentException if either string missing * @return the new string */ public static String interleave2(String s1, String s2) { if( s1 == null || s2 == null ){ throw new IllegalArgumentException(); } String s3 = ""; // length of the shortest string int minlen = Math.min(s1.length(), s2.length()); for(int i = 0 ; i < minlen ; i++) { s3 += s1.charAt(i); s3 += s2.charAt(i); } // the longest string String maxstr = s1.length() > s2.length() ? s1 : s2; for(int i = minlen ; i < maxstr.length() ; i++) { s3 += maxstr.charAt(i); } return s3; } /** * Interleaves the characters of two strings by taking one character at a * time, starting with the first string. * e.g "abc" and "defghi" becomes * "adbecfghi". * * This implementation uses an array of characters instead of * StringBuilder. This would have been necessary if StringBuilder was * not available. * * Given strings of length N and M, the time complexity is O(N+M) since * a single array with enough space is allocated. No reallocation needed. * Each array index is written to exactly once. * * @param s1 the 1st string * @param s2 the 2nd string * @throws IllegalArgumentException if either string missing * @return the new string */ public static String interleave3(String s1, String s2) { if( s1 == null || s2 == null ){ throw new IllegalArgumentException(); } // create an array for all characters in the new string char[] s3 = new char[s1.length() + s2.length()]; // length of the shortest string int minlen = Math.min(s1.length(), s2.length()); int i = 0; while(i < minlen) { s3[2*i] = s1.charAt(i); s3[2*i+1] = s2.charAt(i); i++; } // the longest string String maxstr = s1.length() > s2.length() ? s1 : s2; assert i == minlen; while(i < maxstr.length()) { s3[minlen + i] = maxstr.charAt(i); i++; } return new String(s3); } private static boolean runtest() { if( ! interleave("abc","defghi").equals("adbecfghi") )return false; if( ! interleave("patrik","anna").equals("paantnraik") )return false; if( ! interleave("anna","patrik").equals("apnantarik") )return false; if( ! interleave2("abc","defghi").equals("adbecfghi") )return false; if( ! interleave2("patrik","anna").equals("paantnraik") )return false; if( ! interleave2("anna","patrik").equals("apnantarik") )return false; if( ! interleave3("abc","defghi").equals("adbecfghi") )return false; if( ! interleave3("patrik","anna").equals("paantnraik") )return false; if( ! interleave3("anna","patrik").equals("apnantarik") )return false; return true; } public static void main(String[] args) { System.out.println("I3: " + (runtest() ? "TEST OK" : "TEST FAILED")); } }