Would there be an approach without using a regular expression?

Question

This is an interview question from http://www.glassdoor.com/Interview/Indeed-Software-Engineer-Interview-Questions-EI_IE100561.0,6_KO7,24.htm , specifically, the problem

"The asked me a method that took in a string and return words up to the max length. There could be any amount of spaces which made it a little tricky "

Here is my solution(with test case)

public class MaxLength {
public static void main(String[] args) {
    List<String> allWords = maxWords("Jasmine has no love  for chris", 2);
    for(String word: allWords){
        System.out.println(word);
    }
}
public static List<String> maxWords(String sentence, int length) {
    String[] words = sentence.trim().split("\\s+");
    List<String> list = new ArrayList<String>();
    for(String word: words) {
        if(word.length() <= length) {
            list.add(word);
        }
    }
    return list;
}

The test ran fine and i got my expected output - no. However during an actual interview, I think the interviewer doesn't expect you to know this regular expression off the top of your head (I didn't had to find it from How do I split a string with any whitespace chars as delimiters?) Is there another approach to this problem without using regular expressions?

A question for [this site?](http://codereview.stackexchange.com/) — TheLostMind, Jan 23 '15 at 08:13
Also, your approach is *inefficient*.. You could do this in one iteration without splitting. — TheLostMind, Jan 23 '15 at 08:16
@TheLostMind Please enlighten me. It made sense me to split so you can like you said, make one pass. — committedandroider, Jan 23 '15 at 08:16
It also works when you just pass an white space: `sentence.trim().split(" ");` — halloei, Jan 23 '15 at 08:17
@committedandroider - The value of `maxLength` can change.. My bad... It will need 2 passes.. — TheLostMind, Jan 23 '15 at 08:19
@halloei TheLostMind said that you don't even have to split. If you can't do, how would you differentiate words? — committedandroider, Jan 23 '15 at 08:19
@TheLostMind So this would be most efficient way to do it then? No other way but to use regular expressions? — committedandroider, Jan 23 '15 at 08:20
I'm voting to close this question as off-topic because it is better ask at [http://codereview.stackexchange.com/](http://codereview.stackexchange.com/) — Jens, Jan 23 '15 at 08:20
If the interviewer doesn't know `\\s+` of the top of his/her head, I suggest you run and don't look back. ;) — Peter Lawrey, Jan 23 '15 at 08:26
stackoverflow is for programming questions though isn't it? I chose to ask on here because theres a lot more users.(more likely to get a response) — committedandroider, Jan 23 '15 at 08:27
@PeterLawrey Like the interviewer doesn't expect the interviewee to know this at the top of his/her head — committedandroider, Jan 23 '15 at 08:27
But @Jens in the future, how do i know if a question is more suitable for code review or stack overflow? It's really hard to distinguish for me — committedandroider, Jan 23 '15 at 08:28
@committedandroider If the interviewer is not looking for the right or best answer, only the answer he/she would have given I would take it as a very bad sign. — Peter Lawrey, Jan 23 '15 at 08:29
@committedandroider if you have a problem with your code (error unexpected behavior) SO is the correct site. If you would like to have improvements on running code codereview.stackexchange.com is the better choise. — Jens, Jan 23 '15 at 08:31
@committedandroider The way I would do it is; stackoverflow.com - I have some code which doesn't work or is incomplete, how do I get it to work, by any means. codereview.com - I have code which works, how to I make it better in some way. — Peter Lawrey, Jan 23 '15 at 08:31
@committedandroider If you give an answer which is more advanced, simpler, clearer than what they expect, they should see it as a good thing, and you should only work in a place where they want to simplest, clearest code, not following the expected bad practice. — Peter Lawrey, Jan 23 '15 at 08:32
@PeterLawrey the reason I asked is because if this was an actual job interview question, I wouldn't know that exact regular expression so I have to find a way around not using one. I guess I could just say I would use a regular expression though. — committedandroider, Jan 23 '15 at 08:37

score 0 · Answer 1 · answered Jan 23 '15 at 08:16

0

You could use the StringTokenizer.

Another, maybe more lengthy approach would be to iterate over the string and use the methods provided by the Character class (Character.isWhiteSpace(char c)) and break the string accordingly.

answered Jan 23 '15 at 08:16

npinti

51,780
5
72
96

score 0 · Accepted Answer · answered Jan 23 '15 at 08:20

0

Try:

    public static List<String> maxWords(String sentence, int length) {
        List<String> list = new ArrayList<String>();
        String tmp = sentence;
        while (tmp.indexOf(" ") != -1) {
            String word = tmp.substring(0,tmp.indexOf(" "));
            tmp = tmp.substring(tmp.indexOf(" ")+1);
            if(word.length() <= length) {
                list.add(word);
            }
        }
        return list;
    }

answered Jan 23 '15 at 08:20

Jens

67,715
15
98
113

This one results in lot of spaces between the words but it does produce the right words though – committedandroider Jan 23 '15 at 08:25
@Jens - because subString creates too many well *subStrings*.. :) and `indexOf()` in worst case has to do `n-k` checks.. I am not saying your answer is wrong (better than using *split*).. I am merely saying that there could be a better answer. :) – TheLostMind Jan 23 '15 at 08:36
@TheLostMind but `split` only works with regex and OP would like to have a solution without using regex. – Jens Jan 23 '15 at 08:39
@Jens - Right. I am saying your answer is better than using `split()`. :) – TheLostMind Jan 23 '15 at 08:40
@Jens - Check my answer :) .. Haven't tried it for all inputs, but you will get what I am trying to say.. – TheLostMind Jan 23 '15 at 09:18
I think in Java 7+ substring is O(N), with N=size of the substring. Since this repeatedly uses substring to take the remainder of the string, the entire operation has time complexity O(N^2) with N=size of the sentence. You could avoid this by tracking a current index in the string, and using the overload of indexOf that takes a starting index, instead of shortening the string on each iteration, and get linear time complexity. – Weeble Jan 23 '15 at 09:31
yeah i don't think this would work because spaces are being processed like words – committedandroider Jan 23 '15 at 20:56

score 0 · Answer 3 · answered Jan 23 '15 at 09:18

Well, you could try something like this : Doesn't create many subStrings() just creates subStrings of "matched" Strings

public class Test {

public static void main(String[] args) {
    String s = "Jasmine has no love  for chris";
    s=s.trim();
    List<String> ls = getMaxLength(s, 3);
    for (String str : ls) {
        System.out.println(str);
    }
}

static List<String> getMaxLength(String s, int length) {
    List<String> ls = new ArrayList<String>();
    int i = 0;
    if (s.charAt(i + length) == ' ' || i + length == s.length()) { // search if first word matches your criterion.
        for (i = 1; i < length; i++) { // check for whitespace between 0 and length

            if (s.charAt(i) == ' ') {
                i = length;
                break;
            }
            if (i == length - 1)
                ls.add(s.substring(0, length));
        }
    }

    for (i = length; i < s.length(); i++) {// start search from second word..
        if (s.charAt(i - 1) == ' ' && i + length < s.length() // if char at  length is space or end of String, make sure the char before the current char is a space.  
                && (s.charAt(i + length) == ' ' || i + length == s.length())) {
            for (int j = i; j < i + length; j++) {
                if (s.charAt(j) == ' ') {
                    i = i + length;
                    break;
                }
                if (j == i + length - 1) {
                    ls.add(s.substring(i, i + length));
                }
            }
        }

    }
    return ls;
} // end of method
}

Would there be an approach without using a regular expression?

3 Answers3