問題描述
Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.
Each letter in the magazine string can only be used once in your ransom note.
Note:
You may assume that both strings contain only lowercase letters.
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
題目分析
本題要求對比兩個字符串ransomNote和magazine绢慢，如果ransomNote中的字符均可從magazine中找到藐唠，并且對應(yīng)的字符個數(shù)不小于magazine序攘，則返回true，否則false。假設(shè)：
ransomNot= "fffbfg"
magazine= "effjfggbffjdgbjjhhdegh"
ransomNot中的所有字符均可以從magazine找到飘哨，并且相應(yīng)的字符個數(shù)均小于magazine中的個數(shù)，故返回true。
注意：字符串可認為只含有小寫字母娩井。
解題思路
本題需要滿足兩個條件：
(1)magazine需要包含ransomNot中所有的字符。
(2)magazine所包含的ransomNot字符相對應(yīng)的數(shù)量不小于ransomNot似袁。
首先從ransomNot中的首個字符開始洞辣，與magazine中的字符逐個比較，若找到第一相同的昙衅，則將magazine中的這個相同的字符替換為除小寫字母外的其他字符（題目中所有字符均只有小寫字母）扬霜，然后將ransomNot中的下一個字符與magazine比較，找到相同的就替換而涉，依次完成ransomNot中所有字符的比較查找著瓶，如果某個字符沒有在magazine中找到，則結(jié)束比較啼县，返回false材原。
需要注意的是，當(dāng)ransomNot為空時季眷，需返回true余蟹。若magazine為空，而ransomNot不為空子刮，則返回false威酒。
代碼(C語言)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h> //bool類型
bool canConstruct(char* ransomNote, char* magazine)
{
int i=0,j=0;
bool flag=true;
int size1=strlen(ransomNote);
int size2=strlen(magazine);
if(size1==0) //ransomNot為空
return true;
if(size1!=0 && size2==0) //magazine為空
return false;
char result[size2];
printf("sizez1=%d",size1);
for (j=0;j<size2;j++)
{
result[j]=magazine[j]; //strcpy(result,magazine)
}
//result = (char* )malloc(sizeof(char)*(size2+1));
for (i=0;i<size1;i++)
{
for (j=0;j<size2;j++)
{
if(ransomNote[i]==result[j]) //逐個比較
{
result[j]='0'; //找到到相同就替換
break;
}
}
if(j==size2) //未找到相同字符，結(jié)束比較，返回false
flag=false;
if(flag==false)
break;
}
return flag;
}
int main()
{
char* ransomNote="a" ;
char* magazine="";
bool flag;
flag=canConstruct( ransomNote, magazine);
printf("flag=%d",flag);
return 0;
}
參考文獻
[1] https://leetcode.com/problems/ransom-note/#/description
[2] http://codecloud.net/16807.html
