程序员面试金典练习3

时间：2021-10-25 11:46:17
题目：确定两字符串乱序同构 时间限制：3秒 空间限制：32768K 热度指数：25850本题知识点： 字符串 算法知识视频讲解

题目描述

给定两个字符串，请编写程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。这里规定大小写为不同字符，且考虑字符串重点空格。

给定一个string stringA和一个string stringB，请返回一个bool，代表两串是否重新排列后可相同。保证两串的长度都小于等于5000。

测试样例：
"This is nowcoder","is This nowcoder"
返回：true
"Here you are","Are you here"
返回：false
我的代码：
package com.Main.dl;

import java.util.ArrayList;
import java.util.Scanner;

import javax.swing.text.StyledEditorKit.ForegroundAction;

public class Same {
    @SuppressWarnings("unused")
public static boolean checkSam(String stringA, String stringB) {
    boolean flag=false;
    if(stringA.length()!=stringB.length()){
    flag=false;
}
    //考虑空格数量
    char[] sa=stringA.toCharArray();
    char[] sb=stringB.toCharArray();
    int counta=0;
    int countb=0;
    for (int i = 0; i < sa.length; i++) {
if(sa[i]== ' '){
counta=counta+1;
}
}
    for (int i = 0; i < sb.length; i++) {
if(sb[i]== ' '){
countb=countb+1;
}
}
    if(countb!=counta){
    flag=false;
}
    //比较两个字符内容是否相等
   //str2分隔后字符串，分隔结束
    String[] strA=stringA.split(" ");
    String[] strB=stringB.split(" ");
    if(strA.equals(strB)){
    flag=true;
    }
    ArrayList<String> sa1=new ArrayList<String>();
    ArrayList<String> sb1=new ArrayList<String>();
    //判断顺序不同的情况
    for (int i = 0; i < strA.length; i++) {
    sa1.add(strA[i]);
}
    for (int i = 0; i < strB.length; i++) {
    sb1.add(strB[i]);
}
    flag=digui(sa1,sb1);
    return flag;
    }
    @SuppressWarnings("unused")
public static boolean digui(ArrayList<String> sa1,ArrayList<String> sb1){
    boolean flag=false;
    for (int i = 0; i < sa1.size(); i++) {
for (int j = 0; j < sb1.size(); j++) {
if(sa1.get(i).toString().equals(sb1.get(j).toString())){
sa1.remove(i);
sb1.remove(j);
digui(sa1,sb1);
}
}
}
    if(sa1.size()==0&&sb1.size()==0){
flag=true;
}
    return flag;
    }
//    给定两个字符串，请编写程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。这里规定大小写为不同字符，且考虑字符串重点空格。
//    给定一个string stringA和一个string stringB，请返回一个bool，代表两串是否重新排列后可相同。保证两串的长度都小于等于5000。
//    测试样例：
//    "This is nowcoder","is This nowcoder"
//    返回：true
//    "Here you are","Are you here"
//    返回：false
    public static void main(String args[]){
     Scanner in=new Scanner(System.in);
       while(in.hasNextLine()){
       String str=in.nextLine();
       //逗号分隔
       String[] str2=str.split(",");
       boolean flag=checkSam(str2[0],str2[1]);
       System.out.println("返回"+flag);
       }
    }
}


哎，题目刚开始理解错了，以为只可以调整一个单词的位置，还专门判断了下空格数量是否相等，通过率只有31%，百度了下，分享一下别人的成果。
第一种思路：
package com.Main.dl;

import java.util.Arrays;
import java.util.Scanner;

public class same4 {
public static boolean checkSam(String stringA, String stringB) {
    if(stringA.length()!=stringB.length()) //长度不相等，返回false
        return false;
    char[] a = stringA.toCharArray(); //把字符串转化为字符数组，然后对字符数组进行排序
    char[] b = stringB.toCharArray();
    Arrays.sort(a);
    Arrays.sort(b);
    stringA = new String(a);
    stringB = new String(b);
    if(stringA.equals(stringB))
        return true;
    else
        return false;
}
public static void main(String[] args) {
// TODO Auto-generated method stub

    Scanner in=new Scanner(System.in);
       while(in.hasNextLine()){
       String str=in.nextLine();
       //逗号分隔
       String[] str2=str.split(",");
       boolean flag=checkSam(str2[0],str2[1]);
       System.out.println("返回"+flag);
       }

}
}

超赞的一种解法，理解起来简单代码量还少。Arrays.sort()
第二种思路，检查两个字符串的各字符数是否相同。我们还可以充分利用变位词的定义–组成两个单词的字符数相同–来实现这个算法。我们只需遍历字母表，计算每个字符的次数。然后，比较这两个数字即可。
public boolean checkSam1(String stringA, String stringB) {
    int lenA = stringA.length();
    int lenB = stringB.length();
    if(lenA != lenB){
        return false;
    }
    int[] strA = new int[256];
    int[] strB = new int[256];
    for(int i = 0; i < lenA; i++){
        strA[stringA.charAt(i)]++;
        strB[stringB.charAt(i)]++;
    }
    for(int i = 0;i<256;i++){
        if(strA[i]!=strB[i]){
            return false;
        }
    }
    return true;
}
知识点：Arrays.sort()
标签：

相关文章