CODEWITHSUNDEEP
javaalgorithm
kicklog
kicklog

Reputation: 109

Java algorithm in linked lists

I have the next classes: (Singly linked list)

public class class CharNode {
    private char _value;
    private CharNode _next;

    public CharNode(char val, CharNode n) {
        _value = val;
        _next = n;
    }

    public CharNode(char val) {
        _value = val;
        _next = null;
    }

    public int getValue() {
        return _value;
    }

    public CharNode getNext() {
        return _next;
    }

    public void setValue(char v) {
        _value = v;
    }

    public void setNext(CharNode node) {
        _next = node;
    }
}

and this class:

public class CharList {
private CharNode _head;

public CharList()
{
    _head = null;
}
 //methods
}

I need to write a method (called "what") that gets two char and returns the amount of possible lists that starts and ends with those char. for example if the linked list is "abbcd" the method what(a,b) will return 2 and the method what(a,c) will return 1. I saw the next solution:

public int what(char start, char end) 
{
    int count = 0, countStart = 0;
    CharNode temp = _head;

    while(temp != null)
    {
        if(temp.getValue() == start){
            countStart++;
            temp = temp.getNext();
            if(temp.getValue() == start && start == end)
                countStart++;
        }

        if(temp.getValue() == end && countStart>0){
            count += countStart;
        } 

        temp = temp.getNext();
    }

    return count;
}

but the problem is that I can't understand how they get the algorithm. In other words, how does it work "mathematical"?

Upvotes: 0

Views: 166

Answers (5)

akiva
akiva

Reputation: 369

Here's a version that does the same in a linear time, it may help you to understand your version: (I did not test it, so I hope it works)

public int what (char start, char end) {
    int count = 0, res = 0;
    for (CharNode p = _head; p != null; p = p.getNext())
        if (p.getValue() == start)
            count++;
        else if (p.getValue() == end)
            res += count;
    return res;
}

Upvotes: 0

Yahya
Yahya

Reputation: 14072

This method searches for a given followed two chars in the List by passing the start and the end chars.

public int what(char start, char end)

The count variable is to calculate the total number of occurrence and repetition of the pair of chars (the start & the end chars). So, if we are looking for ab in abcabc the count will be incremented twice because it found the pair ab two times.

int count = 0,

And to count the one occurrence in case it could pass the two tests which are the start & the end chars are found followed by each other, we use: 

countStart = 0;

The program starts from the head of the list and continues searching until there is no next node! That means temp.getNext() will return null!

CharNode temp = _head;
while(temp != null)
   .....................
   CharNode temp = _head;

Now for every current value, if it's the start char, proceed and start counting. Otherwise and in all cases - as long as there is next node - get the next node temp = temp.getNext();

Check then for the next node, and assign it to temp, if it's current value (next node's current value) equals start char AND start char is similar to end char complying to the user's request =, example: search for aa in abcaad, also increment the startCounter to announce finding it and to include it in the final result. 

if(temp.getValue() == start && start == end)
    countStart++;
}

Now, we're still in the next node, so it's value should equals the end char whether the start and end chars similar or not. but to include the occurrence of the start char to be mandatory exact before the end char, we need to check if countStart bigger than zero, that means the previous start char has already been found. If so, add the one occurrence to the total and increment total count.

if(temp.getValue() == end && countStart>0){
        count += countStart;
}

At the end return total count

return count;

Upvotes: 0

Michael
Michael

Reputation: 44150

As I stated in the comments, their implementation is a bit strange to me. Hopefully mine makes more sense.

The idea is to simply iterate through until you find a valid start character, then count all the valid end points from then on. Do the same until you reach the end of the list.

public int what(char start, char end) 
{
    int count = 0;
    CharNode currentNode = _head;

    while(currentNode != null)
    {
        if(currentNode.getValue() == start)
        {
            CharNode potentialEnd = currentNode.getNext();

            while (potentialEnd != null)
            {
                if(potentialEnd.getValue() == end) count++;

                potentialEnd = potentialEnd.getNext();
            }
        }
        currentNode = currentNode.getNext();
    }

    return count;
}

Here's a runnable example.

Upvotes: 0

zThulj
zThulj

Reputation: 149

The answer algorithm that you've posted :

Each time you find the start character, you increase the counter of "how many start" you've found.

And then, each time you find the 'end' character, you know that you have to add the current counter number of word, corresponding to the number of 'start' character found before this 'end' character.

Example :

For this string : 'ababab'

  • The first 'b' will give us 1 word because he has only 1 'a' before
  • The second 'b' will give us 2 words because he has 2 'a' before
  • The third 'b' will give us 3 words because he has 3 'a' before

Upvotes: 1

D M
D M

Reputation: 1410

Well, let's look at the various sections of code.

int count = 0, countStart = 0;
CharNode temp = _head;

The above code just does simple initializations.

while(temp != null)
{
 // ....
    temp = temp.getNext();
}

The above code loops through your list.

    if(temp.getValue() == start){
        countStart++;

The above code keeps track of how many possible starting places there are so far.

    if(temp.getValue() == end && countStart>0){
        count += countStart;
    }

The above code says that when there's an end character, the count is increased by the number of starting characters so far. (Checking whether countStart>0 is actually not necessary, since if it was 0 you'd just add 0, but it doesn't hurt anything.) This makes sense - if you have aaa, then a b at that point would add 3 possibilities.

        temp = temp.getNext();
        if(temp.getValue() == start && start == end)
            countStart++;

The above code appears to be an attempt to account for the special case of the start and end characters being the same. I am NOT convinced that this section of code is correct - frankly, I think it introduces bugs in the case where start and end are different, by using getNext() out of turn.

Upvotes: 0

Related Questions