
Split Your String !
Given a string with no spaces in it, how would you split the strings and insert spaces? That’s one of the simple looking yet very vague requirement and is sometimes asked in the interview.
You need to either make assumptions or seek clarifications on many things.
- Can the String to split be null? Can it be blank?
- Where are the words to compare to located? Is there a dictionary, is there a list of words? Do the words reside in a file?
- Can the unslpit string contain more than two words?
- And many others.
In the following program that I have written, I have assumed that the string to split can be null, the words to lookup are located in a HashMap and the unsplit word contains only two words (You will see that when I am passing a three word string, the program cannot split the string). Another assumption is that all the words in the HashMap are uppercase and the splitting is case insensitive.
package com.icodejava.blog.datastructure; import java.util.HashMap; import java.util.Map; /** * @author Kushal Paudyal * www.icodejava.com * Created On - Feb 15, 2014 * Last Modified On - Feb 15, 2014 */ public class StringSplitter { private static final Map<String, String> DICTIONARY = new HashMap<String, String>(); public static void main(String args[]) { DICTIONARY.put("GOOGLE", "GOOGLE"); DICTIONARY.put("INTERVIEW", "INTERVIEW"); DICTIONARY.put("QUESTION", "QUESTIONS"); String stringToSplit = "interviewquestions"; splitString(DICTIONARY, stringToSplit); stringToSplit = "googleinterviewquestions"; splitString(DICTIONARY, stringToSplit); //Let's try on more with null string. splitString(DICTIONARY, null); } private static void splitString(Map<String, String> LOOKUP_DICTIONARY, String stringToSplit) { boolean splitSuccessful = false; if (stringToSplit != null && stringToSplit.length() > 0) { for (int index = 0; index < stringToSplit.length(); ++index) { String leftSubstring = stringToSplit.substring(0, index); String rightSubString = stringToSplit.substring(index); System.out.println("LEFT: " + leftSubstring + " RIGHT: " + rightSubString); if (DICTIONARY.containsValue(leftSubstring.toUpperCase()) && DICTIONARY.containsValue(rightSubString.toUpperCase())) { System.out.println("MATCH FOUND. SPLIT SUBSTRING: " + leftSubstring + " " + rightSubString + "\n\n"); splitSuccessful = true; break; } } } if (!splitSuccessful) { System.out.println("Could not split the word! Not found in dictionary\n\n"); } } }
Here is the output of running above piece of code.
LEFT: RIGHT: interviewquestions LEFT: i RIGHT: nterviewquestions LEFT: in RIGHT: terviewquestions LEFT: int RIGHT: erviewquestions LEFT: inte RIGHT: rviewquestions LEFT: inter RIGHT: viewquestions LEFT: interv RIGHT: iewquestions LEFT: intervi RIGHT: ewquestions LEFT: intervie RIGHT: wquestions LEFT: interview RIGHT: questions MATCH FOUND. SPLIT SUBSTRING: interview questions LEFT: RIGHT: googleinterviewquestions LEFT: g RIGHT: oogleinterviewquestions LEFT: go RIGHT: ogleinterviewquestions LEFT: goo RIGHT: gleinterviewquestions LEFT: goog RIGHT: leinterviewquestions LEFT: googl RIGHT: einterviewquestions LEFT: google RIGHT: interviewquestions LEFT: googlei RIGHT: nterviewquestions LEFT: googlein RIGHT: terviewquestions LEFT: googleint RIGHT: erviewquestions LEFT: googleinte RIGHT: rviewquestions LEFT: googleinter RIGHT: viewquestions LEFT: googleinterv RIGHT: iewquestions LEFT: googleintervi RIGHT: ewquestions LEFT: googleintervie RIGHT: wquestions LEFT: googleinterview RIGHT: questions LEFT: googleinterviewq RIGHT: uestions LEFT: googleinterviewqu RIGHT: estions LEFT: googleinterviewque RIGHT: stions LEFT: googleinterviewques RIGHT: tions LEFT: googleinterviewquest RIGHT: ions LEFT: googleinterviewquesti RIGHT: ons LEFT: googleinterviewquestio RIGHT: ns LEFT: googleinterviewquestion RIGHT: s Could not split the word! Not found in dictionary Could not split the word! Not found in dictionary