目录

牛客_对称之美_哈希

题目解析

C++代码

Java代码

---

牛客_对称之美_哈希

对称之美 (nowcoder.com)

描述：
        给出n个字符串，从第1个字符串一直到第n个字符串每个串取一个字母来构成一个新字符串，新字符串的第i个字母只能从第i行的字符串中选出，这样就得到了一个新的长度为n的字符串，请问这个字符串是否有可能为回文字符串？

---

题目解析

C++代码

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
    int T = 0;
    cin >> T;
    while(T--)
    {
        int n = 0;
        cin >> n;
        vector<string> vStr(n);
        for(int i = 0; i < n; ++i)  
        {
            cin >> vStr[i];
        }
        // 枚举最左边的每一个字符，和最右边的每一个字符相比，有一样的就是true
        int left = 0, right = n - 1;
        while(left < right)
        {
            bool flag = false;
            for(auto& e1 : vStr[left])
            {
                for(auto& e2 : vStr[right])
                {
                    if(e1 == e2)
                    {
                        flag = true;
                        break;
                    }
                }
                if(flag)
                    break;
            }
            if(!flag)
            {
                cout << "No" << endl;
                break;
            }
            ++left;
            --right;
        }
        if(left >= right)
            cout << "Yes" << endl;
    }
    return 0;
}

Java代码

import java.util.*;
public class Main
{
    public static boolean check(boolean[][] hash, int left, int right)
    {
        for(int i = 0; i < 26; i++)
        {
            if(hash[left][i] && hash[right][i])
                return true;
        }
        return false;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while(t-- != 0)
        {
            int n = in.nextInt();
            // hash[i][j] 表⽰第 i 个字符串，j 字符是否出现过
            boolean[][] hash = new boolean[n][26]; 
            for(int i = 0; i < n; i++)
            {
                char[] s = in.next().toCharArray();
                for(char ch : s)
                {
                    hash[i][ch - 'a'] = true;
                }
            }

            int left = 0, right = n - 1;
            while(left < right)
            {
                if(!check(hash, left, right))
                    break;
                left++;
                right--;
            }

            if(left < right)
                System.out.println("No");
            else
                System.out.println("Yes");
        }
    }
}