A Journey 2 Eternity

Archive for the ‘C/C++’ Category

char* StrStr(const char *str, const char *target) 
{
	char *cp = (char *) str;
	char *s1, *s2;

	if ( !*target ) {
		return ((char *)str);
	}

	while (*cp)
	{
		s1 = cp;
		s2 = (char *) target;

		while ( *s1 && *s2 && (*s1 == *s2) ) {
			++s1;
			++s2;
		}

		if (!*s2) {
			return cp;
		}

		++cp;
	}

	return NULL;
}
Tags: ,

Implement a method to perform basic string compression using the counts of repeated characters. For example string “aabcccccaaa” would become “a2b1c5a3“. If the compressed string would not become smaller then original string then return the original string.

 int CountCompression(string str)
{
	char last = str.at(0);
	int size = 0, count = 1;

	for (int i = 1; i < str.length(); i++)
	{
		if(str.at(i) == last) {
			count++;
		} else {
			last = str.at(i);
			size += 1 + to_string(count).length();
			count = 1;
		}
	}

	// we need to count the very last set of repeated character sets
	size += 1 + to_string(count).length();

	return size;
}

string Compress(string str)
{
	int size = CountCompression(str);
	if(size >= str.length())
		return str;

	string compressStr;
	char last = str.at(0);
	int count = 1;

	for (int i = 1; i < str.length(); i++)
	{
		if (str.at(i) == last) {
			count++;
		} else { // insert char count and update the last char
			compressStr += last;
			compressStr += to_string(count);
			last = str.at(i);
			count = 1;
		}
	}

	// we need to update the very last set of repeated character sets
	compressStr += last;
	compressStr += to_string(count);

	return compressStr;
}
Tags: ,

We are going to write a method to replace all spaces in a string with “%20”. We assume that the string have sufficient space.

void ReplaceSpaces(char *str) 
{
	int length = strlen(str);
	int nSpaces = 0, newLength = 0;
	for (int i = 0; i < length; i++)
	{
		if(str[i] == ' ') ++nSpaces;
	}

	newLength = length + nSpaces * 2;
	str[newLength] = '\0';

	for (int i = length - 1 ; i >= 0; i--)
	{
		if (str[i] == ' ')
		{
			str[newLength - 1] = '0';
			str[newLength - 2] = '2';
			str[newLength - 3] = '%';
			newLength -= 3;
		} else {
			str[newLength - 1] = str[i];
			newLength -= 1;
		}
	}
}
Tags: ,

We are going to write a method to decide if one is a permutation of the other (i.e GOD is a permutation of DOG)

bool IsPermutation(const string &s, const string &t)
{
	if (s.length() != t.length()) {
		return false;
	}

	int letters[256];
	for (int i = 0; i < 256; i++) {
		letters[i] = 0;
	}

	// count the number of each char in s
	for (unsigned int i = 0; i < s.length(); i++) {
		letters[s.at(i)]++;
	}

	for (unsigned int i = 0; i < t.length(); i++) {
		int c = t.at(i);
		if(--letters[c] < 0) {
			return false;
		}
	}

	return true;
}
bool IsUniqueChars(const string &str)
{
	if(str.length() > 256) return false;

	bool char_set[256];
	for (unsigned int i = 0; i < 256; i++)
	{
		char_set[i] = false;
	}

	for (unsigned int i = 0; i < str.length(); i++)
	{
		int val = str.at(i);
		if(char_set[val]) return false;
		char_set[val] = true;
	}

	return true;
}
Tags: ,
void ReverseStringWithArrayScript(char* str)
{
  char* end = str;
  char tmp;
  int length = 0;

  if(str) {
    while (*end++) { // find the end of str and length
      ++length;
    }
    --end; // set one char back, since last char is null

    for(int i = 0, j = length - 1; i < (length / 2); i++, j--) {
      tmp = str[i];
      str[i] = str[j];
      str[j] = tmp;
    } // end for loop....
  } // end nullptr checking loop....
}

void ReverseString(char* str)
{
  char* end = str;
  char tmp;

  if(str) {
    while (*end) { // find the end of str
      ++end;
    }
    --end; // set one char back, since last char is null

    while (str < end) {
      tmp = *str;
      *str++ = *end;
      *end-- = tmp;
    } // end while loop....
  } // end nullptr checking loop....
}
Tags: ,

Sometimes we have needed to compare a Wild-Card string in a given string. Here is a handy function for doing this:

int WildCmp(const TCHAR* wild, const TCHAR* string)
{
	const TCHAR *cp = NULL, *mp = NULL;

	while ((*string) && (*wild != ‘*’)) {
		if ((*wild != *string) && (*wild != ‘?’)) {
			return 0;
		}
		wild++;
		string++;
	}

	while (*string) {
		if (*wild == ‘*’) {
			if (!*++wild) {
				return 1;
			}

			mp = wild;
			cp = string+1;
		} else if ((*wild == *string) || (*wild == ‘?’)) {
			wild++;
			string++;
		} else {
			wild = mp;
			string = cp++;
		}
	}

	while (*wild == ‘*’) {
		wild++;
	}

	return !*wild;
}

Pages

Categories

August 2017
M T W T F S S
« Aug    
 123456
78910111213
14151617181920
21222324252627
28293031  

Blog Stats

  • 27,261 hits