Pages

Monday, April 07, 2008

reverse the words in a sentence using C# (managed code)

Note: The assumption here is that the words are delimited by a single space. This program could be easily modified to work for multiple spaces in the sentence.

Code snippet:

using System;
using System.Collections;

public class Reversal
{
    public string Reverse(string words)
    {
        //find each word and push it in to stack.
        Stack myStack = new Stack();
        //count the number of the spaces in the sentence.
        StringBuilder sb = new StringBuilder();
        //array
        int size = 0;

        //get the total # of words by using delimiter ' '
        for(int i = 1; i < words.Length -1 ; i++)
        {
            if(words[i] == ' ')
            {
                size++;
            }
        }

        //temp string
        string [] temp = new string [size];
        //split the words using delimiter " "
        temp = words.Split(' ');

        //push all the words from the begining in to
        //the stack except for the last word
        for (int i = 0; i < size; i++)
        {
            myStack.Push(temp[i]);
        }

        //take care of the last word
        int lastOccuranceOfSpace = words.LastIndexOf(' ');

        //get the last word from the input.
        String lastWord = words.Substring(++lastOccuranceOfSpace);
        //push the last word
        myStack.Push(lastWord);

        //pop the stack as you will get the items in reverse order
        for (int i = 0; i < size+1; i++)
        {
            string tmp = myStack.Pop();
            StringBuilder sb1 = new StringBuilder();
            //reverse each word you get
            for (int j = tmp.Length - 1; j >= 0; j--)
            {
                sb1.Append(tmp[j]);
            }
            sb1.Append(" ");
            //add it to the final string
            sb.Append(sb1);
        }

    //now sb contains the input in reverse order
    return sb.ToString();
    }
}

class Program
{
    static void Main(string[] args)
    {
        Reversal r = new Reversal();
        string reversedString = r.Reverse("hello this is ram's code");
        System.Console.WriteLine("The reversed string is:" + reversedString);
    }
}

Friday, April 04, 2008

Ever stumbled by a palindrome interview question?

Look here you will find what is required to deal with palindromes.

Here’s a blog that refers the suffix tree and palindrome, and I quote:

“Interestingly, the algorithms for finding palindromes developed by computational biologists generally use suffix trees, and both space and time consumption seem to be worse compared with the algorithm I give in this blog message.”

http://johanjeuring.blogspot.com/2007/08/finding-palindromes.html

and also

http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/

Suffix tree to search the longest duplicated substring
http://www.ddj.com/architect/184404588