首页 > 试题广场 >

实现以下函数,该函数输出两个字符串中不同的的字符,如果字符a

[问答题]
dif(String str1,String str2);
输出两个字符串中不同的的字符,如果字符a在str1中出现,而没有在str2当中出现,则输出-a.相反,则输出+a;
字符串当中重复的子字符串不输出。 abcde,bcde 输出-a dabc, aabcef 输出+a,-d,+e,+f 如 abcdefe,aabcadef输出+a,+a,-e;

void Compare(string s1,string s2)
{
string res;
if(s1.empty() || s2.empty())
return ;
multiset<char> m1,m2;

for(int i=0;i<s1.size();++i)
{
m1.insert(s1[i]);
}
for(int i=0;i<s2.size();++i)
{
m2.insert(s2[i]);
}

for(int i=0;i<s1.size();++i)
{
char ch = s1[i];
if(m1.count(ch) != m2.count(ch))
{
int diff = m1.count(ch) - m2.count(ch);
if(diff < 0)
{
while(diff++ < 0)
res = res + "+" + ch + ",";
//cout<<"+"<<ch<<",";
}
else
{
while(diff-- > 0)
//cout<<"-"<<ch<<",";
res = res + "-"+ch+",";
}
m1.erase(s1[i]);
m2.erase(s1[i]);
}
}


for(int i=0;i<s2.size();++i)
{
char ch = s2[i];
if(m2.count(ch) != m1.count(ch))
{
int diff = m2.count(ch) - m1.count(ch);
if(diff < 0)
{
while(diff++ < 0)
//cout<<"-"<<ch<<",";
res =  res + "-"+ch+",";
}
else
{
while(diff-- > 0)
//cout<<"+"<<ch<<",";
res =  res + "+"+ch+",";
}
m1.erase(s2[i]);
m2.erase(s2[i]);
}
}
string r;
r.assign(res.begin(),res.end()-1);
cout<<r<<endl;
return ;
}

发表于 2015-09-16 21:47:34 回复(0)
public class StringDifferent
{

    public static void main(String[] args)
    {
        StringDifferent sd = new StringDifferent();
        String res = null;
        res = sd.strDif("abcde", "bcde");
        System.out.println(res);
        res = sd.strDif("dabc", "aabcef");
        System.out.println(res);
        res = sd.strDif("abcdefg", "abcdefg");
        System.out.println(res);
        res = sd.strDif("abfg", "abcdefg");
        System.out.println(res);
        res = sd.strDif("afsdlf", "sdlfajsdlfjsd");
        System.out.println(res);
    }

    //这道题目相当于最长公共子序列的改进版,字符串进行二维存储了之后,就沿着相应的规则下来
    //这样做不知道对不对,只能这样写了
    String strDif(String str1, String str2)
    {
        StringBuilder sb = new StringBuilder();
        String tmp = null;
        //                if(str1.length()>str2.length())
        //                {
        //                        tmp = str1;
        //                        str1 = str2;
        //                        str2 = tmp;
        //                }
        int dp[][] = new int[str1.length() + 1][str2.length() + 1];
        int len1 = str1.length();
        int len2 = str2.length();
        //进行dp的方法
        for (int i = 1; i <= len1; i++)
        {
            for (int j = 1; j <= len2; j++)
            {
                if (str1.charAt(i - 1) == str2.charAt(j - 1))
                {
                    dp[j] = dp[i - 1][j - 1] + 1;
                }
            }
        }
        //                for(int i=0;i<=len1;i++)
        //                {
        //                        for(int j=0;j<=len2;j++)
        //                        {
        //                                System.out.print(dp[j]+",");
        //                        }
        //                        System.out.println();
        //                }
        int i = len1, j = len2;
        //如何获取其中的字符串
        while (i >= 0 && j >= 0)
        {
            if (dp[j] == 0)
            {
                if (i < j)
                {
                    tmp = "+" + str2.charAt(j - 1);
                    sb.insert(0, tmp);
                    j--;
                }
                else
                {
                    //判断到头的情况
                    if (i == j && j == 0)
                    {
                        break;
                    }
                    tmp = "-" + str1.charAt(i - 1);
                    sb.insert(0, tmp);
                    i--;
                }
            }
            else
            {
                i--;
                j--;
            }
        }
        return sb.toString();
    }
}

发表于 2014-11-13 21:36:54 回复(0)