PROBLEM LINK:
Setter: mayureshpatle
Tester: mayureshpatle
Editorialist: mayureshpatle
DIFFICULTY:
EASY
PREREQUISITES:
Strings
PROBLEM:
Given 2 strings A and B, determine if they represent same word. If yes, then print “same” else print “different” and the index of first differing character.
EXPLANATION:
Start with first index and increment index till the characters are same or any one or both of the strings end. To check if the characters are same or not we can:
- compare the values of (ASCII(c) - ASCII('A')) if c is an Upper Case character or (ASCII(c) - ASCII('a')) if c is a Lower Case character of any string.
- check if the difference in ASCII Values of characters is either 0 or 32. If it is, then these are same otherwise different.
If both strings reached their ends then they are same, otherwise they are different and the first differing index is the current index.
Time Complexity: O(min(|A|,|B|)) for each testcase.
ALTERNATE EXPLANATION:
Convert both strings A and B to upper case or lower case and compare them directly.
If A \neq B, add any end marker (non-alphabet) symbol at the end of smaller string if both stings have different length. (This ensures that the index will not go out of range before getting different characters in both strings.) Now start with first index and increment the index till the characters are same. Print the current index.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int ind(char c)
{
if('A'<=c && c<='Z') return c-'A';
if('a'<=c && c<='z') return c-'a';
return -1;
}
int main()
{
int t,i;
string a,b;
cin>>t;
while(t--)
{
cin>>a>>b;
for(i=0;a[i] && b[i] && ind(a[i])==ind(b[i]);++i);
if(a[i]=='\0' && b[i]=='\0')
cout<<"same";
else
cout<<"different "<<i+1;
cout<<endl;
}
return 0;
}
Alternate Solution
for _ in range(int(input())):
s,t=input().lower(),input().lower()
if s==t: print('same')
else:
if len(s)<len(t): s+='$'
elif len(s)>len(t): t+='$'
i=0
while s[i]==t[i]: i+=1
print('different',i+1)