Placement Practice | Strings - I

In this blog, we will discuss the most asked topic in the placement process that is Strings.

Introduction to Strings

They are defined as a stream of characters.

Different programming languages have different ways of using and declaring Strings.

Strings in C/C++

• In C/C++, Strings are declared as an array of characters.

• The main difference between a character array and a string is that the string is terminated with a special character '\0'

Declaration:

char string_name[size];

In the above syntax char is the datatype, string_name is any name given to the string, and size is used to define the length of the string.

Initialization:

char str[] = "Programmersdoor";

char str[15] = "Programmersdoor";

char str[] = {'P','r','o','g','r','a','m','m','e','r','s','\0'};

char str[15]= {'P','r','o','g','r','a','m','m','e','r','s','\0'}

std::string class in C++

C++ has in its definition a way to represent the sequence of characters as an object of a class. This class is called std::string.

The String class stores the characters as a sequence of bytes with the functionality of allowing access to the single-byte character.

string Class vs Character array:

• A character array is simply an array of characters that can be terminated by a null character.

• The size of the character array has to allocated statically, more memory cannot be allocated at run time if required. Unused allocated memory is wasted in case of a character array. In the case of strings, memory is allocated dynamically. More memory can be allocated at run time on demand. As no memory is preallocated, no memory is wasted.

• Implementation of the character array is faster than std:: string. Strings are slower when compared to implementation than the character array.

• Character array does not offer many inbuilt functions to manipulate strings. String class defines a number of functionalities that allow manifold operations on strings.

Declaration:

string string_name = "Programmersdoor";

Strings in Java

A string is a sequence of characters. In java, objects of String are immutable which means a constant and cannot be changed once created.

Declaration:

a) Using String literal:

String s = "Programmersdoor";

b) Uisng new keyword:

String s = new String("Programmersdoor");

String methods in java:

• int length(): Returns the number of characters in the String.

"Programmersdoor".length(); //returns 15

• Char charAt(int i): Returns the characters at i-th index.

"Programmersdoor".charAt(4); //returns 'g'

• String substring(int i): Returns the substring from i-th index character to end.

"Programmersdoor".substring(11); //returns "door"

• String substring(int i, int j): Returns the substring from i-th to j-th index character to end.

"Programmersdoor".substring(2, 5); // returns “ogra”

• String concat(String str): Concatenates specified string to the end of this string.

String s1 = "Programmer";

String s2 = "door";

String out = s1.concat(s2); //returns "Programmersdoor"

• int indexOf(String s): Returns the index within the string of the first occurrence of the specified string.

String s = "Blog Learn Blog";

int res = s.indexOf("Learn"); //returns 5

• int indexOf (String s, int i): Returns the index within the string of the first occurrence of the specified string, starting at the specified index.

String s = "Blog Share Blog";

int res = s.indexOf('a',3); //returns 7

• int lastIndexOf(String s): Returns the index within the string of the last occurrence of the specified string.

String s = "Blog Share Blog";

int output = s.lastIndexOf('a'); //returns 7

• boolean equals( Object otherObj): Compares this string to the specified object.

Boolean res = "Program".equals("Program"); //returns true

Boolean res = "Programmersdoor".equals("programmersdoor"); //returns false

• boolean equalsIgnoreCase(String anotherString): Compares string to another string, ignoring case considerations.

Boolean res = "Program".equalsIgnoreCase("Program"); 
//returns true 

Boolean res = "Programmersdoor".equalsIgnoreCase("programmersdoor"); //returns true

• int compareTo(String anotherString): Compares two string lexicographically.

int out = s1.compareTo(s2);  
// where s1 ans s2 are
// strings to be compared

This returns difference s1-s2. 
If :
out < 0  // s1 comes before s2
out = 0  // s1 and s2 are equal.
out > 0   // s1 comes after s2.

• int compareToIgnoreCase( String anotherString): Compares two string lexicographically, ignoring case considerations.

int out = s1.compareToIgnoreCase(s2);  
// where s1 ans s2 are 
// strings to be compared

This returns difference s1-s2. 
If :
out < 0  // s1 comes before s2
out = 0   // s1 and s2 are equal.
out > 0   // s1 comes after s2.

• String toLowerCase(): Converts all the characters in the String to lower case.

String word1 = “PROGRAMMERSDOOR”;

String word2 = word1.toLowerCase(); //returns “programmersdoor"

• String toUpperCase(): Converts all the characters in the String to upper case.

String word1 = "programmerdoor";

String word2 = word1.toUpperCase(); //returns "PROGRAMMERSDOOR"

• String trim(): Returns the copy of the String, by removing whitespaces at both ends. It does not affect whitespaces in the middle.

String word1 = " Learn Share Learn ";

String word2 = word1.trim(); //returns "Learn Blog Learn"

• String replace(char oldChar, char newChar): Returns new string by replacing all occurrences of oldChar with newChar.

String s1 = “prateek“;

String s2 = “prateek”.replace(‘e’ ,’i’); //returns "pratiik"

---

Pattern Searching Algorithm

Given a text and pattern, we have to write a search function that prints all the occurrences of patterns in the text. Assume that n > m.

Example:

Input:  txt[] = "Hello i am prateek"
        patrn[] = "am"
Output: Pattern found at index 8

Input:  txt[] =  "AABAACDAACAABA"
        patrn[] =  "AABA"
Output: Pattern found at index 0
        Pattern found at index 10

Naive Pattern Searching:

The idea is to slide the pattern over text one by one and check for a match. If a match is found, then slides by 1 again to check for subsequent matches.

That is check for the match of the first character of the pattern in the string, if it matches then check for the subsequent characters of the pattern with the respective characters of the string. If a mismatch is found then move forward in the string.

Below is the implementation of the above approach using C++:

#include<bits/stdc++.h>
using namespace std;

void search(char* patrn, char* txt)
{
    int M = strlen(patrn);
    int N = strlen(txt);

    for (int i = 0; i <= N - M; i++) {
        int j;

        for (j = 0; j < M; j++)
            if (txt[i + j] != patrn[j])
                break;

        if (j == M) 
            cout << "Pattern found at index "
                 << i << endl;
    }
}

int main()
{
    char txt[] = "AABAACDAACAABA";
    char patrn[] = "AABA";
    search(patrn, txt);
    return 0;
}

Output:

Pattern found at index 0         
Pattern found at index 10

---

Happy Coding!

Follow us on Instagram @programmersdoor

Join us on Telegram @programmersdoor

Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.

Follow Programmers Door for more.

#blog #interview #placement #learn #computer #science