Thread: Java dictionary search algorithm

okay lets start with ("binary", "bind", 4) for n=4 if s.charAt(i) comes before t.charAt(i) it should return true if not then return false. but I'm not sure how to implement this.
would it be something like this

if (s.charAt(i)<t.charAt(i)){
return true;}
else{
return false;}

--- Update ---

Originally Posted by drdre

okay lets start with ("binary", "bind", 4) for n=4 if s.charAt(i) comes before t.charAt(i) it should return true if not then return false. but I'm not sure how to implement this.
would it be something like this

if (s.charAt(i)<t.charAt(i)){
return true;}
else{
return false;}

Never mind ive got the first 3 bullet points working but when I test the last 2 bullet points don't appear on my console and I get this error:
Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 3
What do I do if the string is less than n.

Originally Posted by Norm

What about if the second one is shorter and less than n?
lessThan("binary", "bit", 4);

That does not happen often with computers. They should always do the same thing every time.

The search done in the loop should only change the boolean variable when the compare fails.
It currently sets it true on one letter and false on another. If it does that, the value will only reflect the last letter it looked at.

Does this solve the problem for this:

What about if the second one is shorter and less than n?
lessThan("binary", "bit", 4);

public boolean lessThan(String s, String t, int n) {
 
        boolean lessThan = false;
 
        if (s.length()<n || t.length()<n){
            if (s.length()<t.length()){
                n=s.length();
            }else if(t.length()<s.length()){
                n=t.length();
            }
        }
        for (int i =0; i<n; i++){
            if (s.charAt(i) == t.charAt(i)){
                lessThan = false;
            }else if (s.charAt(i)<t.charAt(i)){
                lessThan = true;
            }
        }return lessThan;
    }

Originally Posted by Norm

Did you test the new length testing logic? Did it work? What if the lengths are both 3 and n is 4?

Now you need to change the setting of the lessThan variable so that its value is not just the results of the last test.
One idea to to exit the loop and the method when the first test fails.
For example test with this:
lessThan("feast", "beast", 4)

Okay all the bullet points now work EXCEPT the 4th one:

lessThan("bin", "binary", 4) gives false in my console which should be true as bin comes before binary
and if I flip both strings to this:
lessThan("binary", "bin", 4) gives true in my console which should be false

For example test with this:
lessThan("feast", "beast", 4)

I get false which is correct


How do I fix the 4th Bullet point I get opposite result for the desired output.

Originally Posted by Norm

Can you describe in words the logic for these two things? Instead of trying to write more code. It is important to design the program before trying to write code.
1)Find the smaller value of these three thing: s.length, t.length, n
2)Compare the characters of the two Strings one at a time to determine which one comes first.

The code does not have any comments so I can not tell what it is supposed to do.
For example, what is the purpose of this statement:

I=n;

Okay for the 4th Bulletpoint:
lessThan("bin", "binary", 4) is true but my console outputs false.

Lets say s="bin" and t="binary", we need to find the shortest length out of these two, S is the shortest and is length=3, hence need to store 3 in n.
But the problem is that the first 3 letters are the same and due to this code in my program:

if (s.charAt(i) == t.charAt(i)){
lessThan = false;

found directly after the for loop. my code causes it to output false as for n=3 letters, they both equal. however bin comes before binary in the dictionary and as a result should output true. this is the problem with my code. however I need that piece of code for words that are not shorter than n that are the same e.g. lessThan("binder", "binding", 4) = false which is correct.

Originally Posted by Norm

Why do that if both lengths are >= to n?

The code currently tests if either String is < n
However it fails if the lengths are both < n because it does not change n.
If either String is < n, use the length of the shorter String or if == lengths, the length of either will do.

Given the number of char to test from above, how to determine if the first String is less than the second String?
What are the logical steps?


What should lessThan("binary", "bin", 4) return? Given the quote, it should be false. How does being equal for the length of the smaller one set the result?

code for find the shorter string:

if (s.length()<n || t.length()<n){
            if (s.length()<t.length()){
                n=s.length();
            }else if(t.length()<s.length()){
                n=t.length();
            }
        }

It compares each length with each-other and stores the shortest word in n.

yes lessThan("binary", "bin", 4) should return false as you said
however lessThan("bin", "binary", 4) should return true as bin comes before binary however my code results it to output false.

1. firstly it finds the length "bin" which is shorter than n which is 4.
2. then stores bins length which is 3 in n.
3. then 3 is passed into the code: (remember i starts from 0, so characters count from 0,1,2)
[code]
for (int i =0; i<n; i++){
//return false if first i characters match
if (s.charAt(i) == t.charAt(i)){
lessThan = false;
[\code]
4. result in output to be false which is wrong.

Originally Posted by Norm

What if the lengths are equal AND less than n? The posted code does not change the value of n.
You don't need the else if test:

   if (x < 2) {
     // process
   }else {
     // here we know that x is >= 2 no need to test with an if
   }

You wrote code instead of English for the logic.
Given the number of characters to test is in n,
what does the logic need to do inside the loop
and after the loop?

if length is equal and less than ill change code to: if (s.length()<=t.length())
so if they're ever equal and less than n output will be false as:
//return false if first i characters match
if (s.charAt(i) == t.charAt(i))