Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 18 of 18

Thread: Java dictionary search algorithm

  1. #1
    Junior Member
    Join Date
    Mar 2019
    Posts
    9
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Java dictionary search algorithm

    You should not use any other String methods apart from length() and charAt(), or the Java binarySearch method.

    boolean lessThan(String s, String t, int n)
    This method should return true if the first n elements of the array s come before the first n elements of the array t in dictionary order. For example, if n is 4:

    • lessThan("binary", "bind", 4) is true, because the first four characters differ, and 'a' is less than 'd'.
    • lessThan("binder", "binding", 4) is false, because the first four characters match.
    • lessThan("binding", "binder", 4) is false, because the first four characters match.
    • lessThan("bin", "binary", 4) is true.
    • lessThan("bit", "binary", 4) is false.



    What I've done so far:
    public boolean lessThan(String s, String t, int n) {
            boolean lessThan = false;
            for (int i =0; i<n; i++){
                if (s.charAt(i) == t.charAt(i)){
                    lessThan = false;
                }else{
                    lessThan = true;
                }
            }return lessThan;
        }
    which only fulfils when first 4 character match outputting false, but ive got no clue on how to implement the 1,4,5th bullet points.
    Last edited by drdre; March 16th, 2019 at 12:11 PM.

  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Java dictionary search algorithm

    Ok, pick one of the items in the list and describe what you think needs to be done to solve it or ask some questions about the problems you are having with it.

    Please edit your post and wrap your code with code tags:

    [code]
    **YOUR CODE GOES HERE**
    [/code]

    to get highlighting and preserve formatting.
    If you don't understand my answer, don't ignore it, ask a question.

  3. The Following User Says Thank You to Norm For This Useful Post:

    drdre (March 16th, 2019)

  4. #3
    Junior Member
    Join Date
    Mar 2019
    Posts
    9
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: 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 ---

    Quote Originally Posted by drdre View Post
    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.

  5. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Java dictionary search algorithm

    What do I do if the string is less than n.
    Control the loop iterations with the minimum of the length of the shortest String and n
    If you don't understand my answer, don't ignore it, ask a question.

  6. #5
    Junior Member
    Join Date
    Mar 2019
    Posts
    9
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Java dictionary search algorithm

    Quote Originally Posted by Norm View Post
    Control the loop iterations with the minimum of the length of the shortest String and n
    Here my updated code:
    public boolean lessThan(String s, String t, int n) {
     
            boolean lessThan = false;
     
            if (s.length()<n){
                n = s.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;
        }
    I no longer get the error message and my console prints out:

    lessThan("binary", "bind", 4) = true
    lessThan("binder", "binding", 4) = false
    lessThan("binding", "binder", 4) = false
    lessThan("bin", "binary", 4) = false
    lessThan("bit", "binary", 4) = false

    The 4th one should be true and 5th one is correct but I assume that's due to chance. What do I implement now?
    Last edited by drdre; March 16th, 2019 at 01:34 PM. Reason: typo

  7. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Java dictionary search algorithm

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

    due to chance
    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.
    If you don't understand my answer, don't ignore it, ask a question.

  8. #7
    Junior Member
    Join Date
    Mar 2019
    Posts
    9
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Java dictionary search algorithm

    Quote Originally Posted by Norm View Post
    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;
        }

  9. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Java dictionary search algorithm

    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)
    If you don't understand my answer, don't ignore it, ask a question.

  10. #9
    Junior Member
    Join Date
    Mar 2019
    Posts
    9
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Java dictionary search algorithm

    Quote Originally Posted by Norm View Post
    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.

  11. #10
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Java dictionary search algorithm

    Can you post the new code and the test case that fails?
    If you don't understand my answer, don't ignore it, ask a question.

  12. #11
    Junior Member
    Join Date
    Mar 2019
    Posts
    9
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Java dictionary search algorithm

    I know the problem with my code as for these:

    My console prints:
    lessThan("bin", "binary", 4) = false (which should be true)
    lessThan("bit", "bitary", 4) = false (which should be true)

    when s.length is shorter than t.length like above n=s.length(); so 3 in this case now cos of this (Whats in bold) causes it to be false as for n=3 (the first 3 letter in each case)they are equal.

    ("bin", "binary", 4)
    ("bit", "bitary", 4)

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


    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;
                    i=n;
                }
            }return lessThan;
        }
    Last edited by drdre; March 16th, 2019 at 02:56 PM.

  13. #12
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Java dictionary search algorithm

    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;
    If you don't understand my answer, don't ignore it, ask a question.

  14. #13
    Junior Member
    Join Date
    Mar 2019
    Posts
    9
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Java dictionary search algorithm

    Quote Originally Posted by Norm View Post
    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.

  15. #14
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Java dictionary search algorithm

    we need to find the shortest length out of these two
    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?

    however bin comes before binary in the dictionary
    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?
    If you don't understand my answer, don't ignore it, ask a question.

  16. #15
    Junior Member
    Join Date
    Mar 2019
    Posts
    9
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Java dictionary search algorithm

    Quote Originally Posted by Norm View Post
    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.

  17. #16
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Java dictionary search algorithm

    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 you don't understand my answer, don't ignore it, ask a question.

  18. #17
    Junior Member
    Join Date
    Mar 2019
    Posts
    9
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Java dictionary search algorithm

    Quote Originally Posted by Norm View Post
    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))

  19. #18
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Java dictionary search algorithm

    I'm not sure what your comments mean for finding the length to scan. You posted one line of code for finding the length, but not all of it.

    Can you post the logic for the search?
    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 you don't understand my answer, don't ignore it, ask a question.

Similar Threads

  1. Beginner program w/ file, arrays and binary search algorithm - HELP!
    By lisagurra in forum What's Wrong With My Code?
    Replies: 1
    Last Post: September 27th, 2018, 09:23 AM
  2. Incorporating a search dictionary
    By seventhCircuit777 in forum What's Wrong With My Code?
    Replies: 0
    Last Post: September 24th, 2018, 05:56 PM
  3. Binary Search Algorithm
    By omgitztmarie in forum What's Wrong With My Code?
    Replies: 1
    Last Post: March 25th, 2014, 06:22 AM
  4. Algorithm for building an dynamic dictionary and auto spell corrector?
    By Dinesh Raja in forum Algorithms & Recursion
    Replies: 7
    Last Post: December 5th, 2013, 08:20 AM
  5. Replies: 0
    Last Post: March 28th, 2010, 01:27 PM

Tags for this Thread